技術共有

[手作業で細断されたデータ構造] 装甲除去/空間の複雑さ

2024-07-12

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

目次

序文

空間/時間の複雑性とは何かを知りたい場合は、データ構造が何であるかを知る必要があります。

これは 2 つのレベルで理解できます。 Douyin で話題になっている国際イベントや雍正軍の装甲撤去など、データは私たちの生活のあらゆるところに存在します。ユーザーが見ることができるのは、Douyin がバックエンド サーバーに保存しているデータです。ただし、これらのデータにはすべて、Douyin のホット検索リストに含まれているという 1 つの特徴があり、このリストは、データがユーザーが閲覧できる固定の場所に確実に存在するように構造化されています。

さらに、データ構造とアルゴリズムは切り離すことができません。先ほど述べたように、データ構造はデータを構造内に定期的に保存するため、その構造からデータに効率的にアクセスする方法がアルゴリズムになります。

時間の複雑さ

アルゴリズムには、時間の複雑さと空間の複雑さが存在します。コンピューターのメモリはますます大きくなっているため、空間の複雑さよりも時間の計算量の方が重要です。それでは、まず時間計算量を理解しましょう

コンセプト

時間計算量、最も重要な言葉は時間です。ここでの時間は、プログラムが実行されている時間を指します。時間計算量が小さければ、アルゴリズムが優れていることが証明されます。時間計算量の計算は関数式 T(N) で表されます。

そこで、このプログラムの時間計算量を事前に計算して、最適解となるコードを書いてみませんか?これにはコンピューターの問題が関係します。

  1. プログラムの実行時間はコンパイル環境と実行マシンの構成に関係するため、たとえば、アルゴリズム プログラムでは古いコンパイラが使用されます。
    新しいコンパイラでコンパイルする場合と、新しいコンパイラでコンパイルする場合では、同じマシン上でも実行時間は異なります。
  2. 同じアルゴリズム プログラムでも、古い低構成マシンと新しい高構成マシンを使用すると実行時間は異なります。
  3. また、時間はプログラムを作成した後にのみテストでき、プログラムを作成する前に理論的思考を通じて計算および評価することはできません。

コードの一部を見てみましょう。

// 请计算⼀下Func1中count语句总共执⾏了多少
次？
void Func1(int N)
{
int count = 0;
for (int i = 0; i < N ; ++ i)
{
for (int j = 0; j < N ; ++ j)
{
++count;
}
}
for (int k = 0; k < 2 * N ; ++ k)
{
++count;
}
int M = 10;
while (M--)
{
++count;
}
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

count の実行回数に基づいてこのコードを見ると、次のようになります。
T (N) = N2 + 2 ∗ N + 10
• N = 10 T(N) = 130
• N = 100 T(N) = 10210
• N = 1000 T(N) = 1002010

このとき、誰かが、int count=0 はカウントされないのかと言いました。

ここで、私たちはコンピューターを過小評価しすぎています。コンピューターの CPU は 1 秒間に数億回実行できます。もちろん、このわずかな時間は無視できます。したがって、私たちが計算した時間計算量は正確ではなく、現時点では、それを表すために新しい記号を使用しています。

ビッグオーの漸近表現

Big O 表記法: 関数の漸近的な動作を記述するために使用される数学記号であり、ここでは推定時間計算量を表すために使用されます。

それでは、ここでも T(N) のようにカウントされますか? そうであれば、それを表すために別の記号を使用する必要はありません。これには、O を数えるルールが含まれます。

  1. 時間計算量の関数式 T(N) では、最上位の項のみが保持され、下位の項は削除されます。これは、N が増加し続けると、結果に対する下位の項の影響がますます小さくなるためです。 Nが無限大の場合は無視して構いません。
  2. 最上位の項が存在し、それが 1 でない場合は、この項の定数係数を削除します。N が無限大の場合、この係数が結果に与える影響はますます小さくなるからです。
  3. T(N) に N 関連項目がなく、定数項目のみがある場合は、すべての加法定数を定数 1 に置き換えます。

次に、上記の T(N)=N^ 2 + 2 ∗ N + 10 を見てください。ここでの最高次数は N2 なので、他の低次を取り除くと、複雑さは (ON^2) になります。

小型チョッパー

// 计算Func3的时间复杂度？
void Func3(int N, int M)
{
int count = 0;
for (int k = 0; k < M; ++ k)
{
++count;
}
for (int k = 0; k < N ; ++
k)
{
++count;
}
printf("%dn", count);
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

ここで、T(N)=M+N です。ここで、M と N は両方とも同じ次数であるため、最初の規則に準拠せず、2 番目と 3 番目の規則にも対応しません。 、つまり o(N+M) ということですが、N が M より大きい場合は O(N) になるのではないかと誰かが尋ねました。N が M より大きいことはどのようにしてわかるのでしょうか。 M が N より大きい場合はどうなるでしょうか。そのため、念のためここに留まります。

// 计算strchr的时间复杂度？
const char * strchr ( const char
 * str, int character)
{
const char* p_begin = s;
while (*p_begin != character)
{
if (*p_begin == '0')
return NULL;
p_begin++;
}
return p_begin;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

ここでは str 内の文字の位置を探しています。ここで知識ポイントを追加します。

  • 私たちの O 計算は、通常、アルゴリズムの最悪の場合の複雑さです。
    ここでは、複雑さの 3 つのレベルに分類できます。
    1. 最良のシナリオ
    文字列の最初の位置にある文字を検索するには、次のようにします。
    F (N) = 1、複雑さは o(1)

2. 平均的な状況:
文字列の途中にある文字を検索するには、次のようにします。
F(N) = N/2,O(N/2)

3. 最悪のシナリオ
文字列の最後の位置にある文字を検索するには、次のようにします。
F(N) = N,O(N) です

// 计算BubbleSort的时间复杂度？
void BubbleSort(int* a, int n)
{
assert(a);
for (size_t end = n; end > 0; --end)
{
int exchange = 0;
for (size_t i = 1; i < end; ++i)
{
if (a[i-1] > a[i])
{
Swap(&a[i-1], &a[i]);
exchange = 1;
}
}
if (exchange == 0)
break;
}
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

ここに画像の説明を挿入します
最悪の場合、上位を保持してn/2を削除(1項目目)、係数(2項目目)を無視するためON^2となります。

void func5(int n)
{
int cnt = 1;
while (cnt < n)
{
cnt *= 2;
}
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

n=2の場合、実行回数は1回となります。
n=4の場合、実行回数は2回となります。
n=16の場合、実行回数は4回となります。
実行回数を x とすると 2
x = n
したがって、実行数: x = log n
したがって、func5 の最悪の場合の時間計算量は次のようになります。
O(log2^n) の

書籍によって表現方法は異なりますが、上記の記述方法に大きな違いはありません。log n を使用することをお勧めします。

空間の複雑さ

空間計算量について注意すべきことは、その計算表現も O で表され、その規則は時間計算量と同じ 3 つの規則に従っていることです。

知らせ

関数の実行時に必要なスタック スペース (パラメーター、ローカル変数、一部のレジスタ情報などの保存) はコンパイル中に決定されるため、スペースの複雑さは主に、関数の実行時に関数によって明示的に適用される追加スペースによって決まります。 。

例1:

// 计算BubbleSort的时间复杂度？
void BubbleSort(int* a, int n)
{
assert(a);
for (size_t end = n; end > 0; --end)
{
int exchange = 0;
for (size_t i = 1; i < end; ++i)
{
if (a[i-1] > a[i])
{
Swap(&a[i-1], &a[i]);
exchange = 1;
}
}
if (exchange == 0)
break;
}
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

関数スタック フレームはコンパイル中に決定されます。
実行時に関数によって要求される追加スペースにのみ注意する必要があります。
BubbleSort の追加アプリケーション スペースは次のとおりです。
Exchange などのローカル変数の数には制限があり、一定量の追加スペースを使用します。
したがって、空間複雑度は O(1) です。

個人プロフィール

彼は 30 年以上テクノロジーの研究に専念しており、Java、linux、javascript、php、css などのさまざまな言語に堪能であり、オープンソース分野で多くの貢献を行っています。将来の参考のために技術開発におけるいくつかの問題を共有する開発者ドキュメント ステーション。

私の連絡先情報

郵便