技術共有

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

目次

1. データ構造の3つの要素

1.1 データ構造に対する操作

1.2 データ構造の格納構造

2. データ型、抽象データ型

3. アルゴリズム

3.1 時間計算量 T(n)

3.2 空間の複雑さ

---

1. データ構造の3つの要素

1.1 データ構造に対する操作

つまり、追加、削除、変更、確認

1.2 データ構造の格納構造

2. データ型、抽象データ型

データの種類:

(1)。アトミックタイプ: bool、int...

(2). 構造タイプ: クラス、構造...

抽象データ型 (ADT):

構造タイプと同様に、ユーザーものみデータ構造を知る必要がある名前およびそれらのデータ間の接続 (関数） できる

3. アルゴリズム

3.1 時間計算量 T(n)

時間計算量が小さいほど、アルゴリズムは優れています

(1) 運用ルール

追加：

複数の項目を追加するの場合、最高次項 (べき乗) のみが保持されます。

T1(n) + T2(m) = T(max(n,m))

乗算：

T1 x T2 = O( f(n) xg(n) )

(2). 一般的な大きさの比較

一般に、最初の 3 つと最後の 3 つを覚えていれば十分です。定数ペアは次数を指します。 

3.2 空間の複雑さ

1GB = 1024*1024*1024 バイトは約 10 億バイト

1GB=1024MB 1MB=1024KB 1KB=1024バイト

実際には、さまざまなデータ型に格納されているバイト数を知る必要はなく、数値として直接格納するだけで、最終的には係数が省略され、係数が の n を含む計算式に変換されます。 1つ。

関数内では、パラメータすべての受信データは、必要なしこれらのパラメーターの数は既知であり、省略できるため (再帰関数を除く)、空間計算量の一部としてカウントされます。

関数内で計算する必要があるのは次のとおりです。関数内での宣言により、変数。

特別：

再帰関数では、データが渡されるたびに、カバーしません元の場所に保存されていますが、新しいアドレス, したがって、再帰関数の空間複雑さを判断したい場合は、再帰の開始点から終了点までのプロセス全体のメモリ使用量を明確にする必要があります。

特に配列の再帰関数に関しては、配列の長さ再帰で発生する変化、その場合、多くの場合、使用する必要があります等差数列の和，