整列

1.アレイとは

関連データを1つの変数にグループ化して管理するデータ構造で、1つの変数に複数の情報を含めることができます.変数にデータが格納されている場合、
複数のデータが格納されている差が並びます.

1.1. 配列宣言の例

js規格

student = new Array();
student[0] = "정재민";
student[1] = "조은미"

ValueとIndexを合わせてElementと呼ぶ.

1.2. C方案の特徴

配列宣言から資料の種類と大きさが指定されています.また、同じタイプのデータを格納して変更するしかなく、要素を削除することはできません.中央の要素を削除すると、インデックスは空のままになります.
並べ替えを宣言するときは、連続したメモリ領域を予約し、データを並べて連続的に格納します.

Cは1つの整数を格納するために4 bバイトを必要とし、上の配列は4つの整数を格納する必要があるため、16バイトのメモリが割り当てられている.

1.3. Pythonリストの特性

Pythonのリスト内部はC配列で生成された資料型である.
appendメソッドでは、配列とは異なり、サイズやデータ型を指定する必要がなく、いつでも新しい値を追加できます.
リストに割り当てられた空間には、変数の値ではなく、各変数の参照値が連続的に格納されます.
*各メモリ領域には、実際の値ではない参照が格納されており、複数のデータ型を格納できます.

2.配列の格納方法とインデックスアクセスについて

C言語例

int numArr[4]; //사용하고 있지 않고 연속적인 16칸 예약
numArr[0] = 2;
numArr[1] = 3
numArr[2] = 5;
numArr[3] = 7;

アレイの要素は、メモリに順次、連続的に記憶する

.

Cをコンパイルすると,配列名(numar)は配列開始時のメモリアドレス値を示す.
=>配列中の値を用いて連続的に格納される点は,以下のように成り立つ.

// 3번 인덱스 접근
numArr배열의 시작주소: 1000
1000 + 4 * 3 = 1012

配列の値を得るには,その値のアドレスを知る必要があり,アドレスは簡単な計算式で求めることができる.
=>どのインデックスにアクセスしても時間の複雑さはO(1)
=>RAMの特性を十分に利用するデータ構造

.

3.シナリオの参照

ナビゲーションは、特定の条件を満たす値のみを検索し、インデックス検索値とは異なる概念

を検索する.

リニアナビゲーション:データを順番に検索するナビゲーション方法

=>特定の条件値を検索するには、アレイの0番のインデックスを最後のインデックスに順次アクセスする必要があります.したがって、アクセスよりも効率的ではない概念

にナビゲートします.

クリア時間の複雑さ

アレイアクセス演算:O(1)

アレイナビゲーション演算:O(n)

アレイに値を格納およびアクセスする方法は、時間的複雑度O(1)のアレイに非常に適している.
特定の条件を満たす値を探索する場合,時間複雑度はO(n)であり,配列の大きさに比例する.

4.静的アレイ、動的アレイの比較

静的スキーム

Cの配列に相当し、大きさは固定されている.

の無駄なメモリ容量を最小限に抑えることができます.

ダイナミック配列

これは

Pythonのリストに相当し,開発者の立場からは配列の大きさは考慮されない.

の状況に応じてサイズを変更する柔軟性はあるが、動的配列自体は静的配列の資料構造である.

5.動的配列の追加演算

配列の最後に新しい値を追加する操作は、追加操作(append operatoin)として定義されます.
動的配列は内部では静的配列によって生成されるデータ型であり,後続の演算では次の2つのケースの数が現れる.

静的アレイにメモリ容量が残っている場合、

の空き領域の一番前のインデックスに値を格納

.

時間複雑度:O(1)

静的アレイにメモリ容量が残っていない場合、メモリを追加するときは

です.

メモリ容量が現在使用されているアレイよりも大きい新しいアレイを作成し、

の新しい値を追加します.

すべての値を既存の配列から新しい配列にコピーし、最後の新しい値

を追加します.

時間の複雑さ
=>アレイ内のすべてのインデックスにアクセスしてO(n)+新しい値O(1):O(n+1)

をコピーする.

6.挿入演算

アレイの末尾にデータを追加するためのappend操作とは異なり、要素を追加する場合、アレイ内の要素の位置にかかわらず、挿入操作と呼ばれます.
挿入演算は、静的配列にスペースがある場合とない場合の2つに分けられます.

配列中間データ挿入演算

静的配列空間が空の場合

n番目のインデックスの後のデータを1つのグリッドに後回しにし、n番目のインデックス・グリッドに空間を作成します.n番インデックスバーに新しいデータ

を挿入する

時間複雑度:1段後退O(n)+挿入データO(1)

静的レイアウトスペースがない場合

の値を追加するには、現在使用されているアレイよりもメモリ領域が大きい新しいアレイ

が作成されます.

既存の値を新しいアレイ

にコピー

n番目のインデックスの後のすべてのデータをn番目のインデックス空間に後方に押し込み、新しいデータ

を挿入する.

時間の複雑さ:新しい配列を作成した後、既存の値O(n)+をコピーして1つ後ろに押すプロセスO(n)+対応するインデックス列データO(1)

を挿入する

6.削除操作

フロントエンドデータクリア時
=>時間複雑度:O(n)

最後にデータを削除した場合
=>時間複雑度:O(1)

ひかくアレイえんざん

追加

(append):最後のインデックス後のアドレス

にデータを追加する
挿入

:任意のインデックスアドレスにデータを追加

削除(delete):既存のアレイを削除した後、メモリの無駄を回避するために内部に新しいアレイ(静的アレイ)を作成します.

配列サイズは固定されており、挿入、削除はできません.