並べ替えられた配列の複雑な計算

Question

現在、私は私の大学のためのプロジェクトをやっています。既知のデータ構造（配列、リンクリスト、BSTなど）を実装しています。たとえば、私にとって最初のものは配列でした。私は配列の途中に要素を追加する時間を測定しました。（さらに値を移動すると、n = n + 1です。もちろん、これはO(n)です。ここでnは要素の数です。 。アレイと、それ（最後に加える）に要素を追加するの先頭に私は（私はSTLまたはboost::を使用することはできません）2つの、簡単なアルゴリズムを持っている：

が先頭に追加：

void array::beginning_append(int value) 
{ 
    int *temp = new int[n + 1]; 
    memcpy(temp + 1, table, sizeof(int) * n); 
    n = n + 1; 
    temp[0] = value; 
    delete[] table; 
    table = new int[n]; 
    memcpy(table, temp, sizeof(int) * n); 
    delete[] temp; 
} 

最後に追加：

void array::append(int value) 
{ 
    int *temp = new int[n + 1]; 
    memcpy(temp, table, sizeof(int) * n); 
    temp[n] = value; 
    n = n + 1; 
    delete[] table; 
    table = new int[n]; 
    memcpy(table, temp, sizeof(int) * n); 
    delete[] temp; 
} 

これらはメソッドまたはarrayクラスです。tableおよびnはこのクラスのメンバーです。今ではそれほど違いはないと思いますが、その時代は同じだと思っていました（500000のような要素の数が多いとQueryPerformanceCounterでチェックしました）、私にはO(n)の複雑さが与えられましたが、 O(n)の計算量が必要ですが、最後に要素を追加または削除すると複雑さはO(1)になるため、要素の数に関係なくconstになります。だから、私はアルゴリズムが悪い場合、私は彼らが不必要なものを行う意味、彼らは要素の数に依存している理由です、または私の講師はちょうど間違っていた君たちをお願いしたいと思い

Answer 1

どちらの複雑さは、次のとおりです。

O（n）

アレイ全体をコピーしているためです。

複雑度の詳細については、memcpy()hereを参照してください。

---

ヒント：簡単tableを指しているメモリを解放し、それがtempをポイントすることによって、2番目のコピーをスキップすることができます。そうすれば、二度ではなく一度だけコピーします。しかしながら、全体的な時間の複雑さは変化しない。

例：

void array::prepend(int value) 
{ 
    int *temp = new int[n + 1]; 
    memcpy(temp + 1, table, sizeof(int) * n); 
    n = n + 1; 
    temp[0] = value; 
    delete[] table; 
    table = temp; 
} 

---

プロチップ：How do you detect/avoid Memory leaks in your (Unmanaged) code?

_{のHunch：realloc()の巧妙な実装では、新しいアレイにブルートmemcpy()より速く実行する必要があります。その理由は、realloc()が配列全体を新しい場所にコピーすることなく配列を拡大/縮小できれば（これは、単純な連続スペースがない場合に発生する可能性があります）、より高速になります。 realloc()は常にO（1）を意味するわけではありません。}

Answer 2

バッファを新しい要素を保持するのに十分な大きさにすると、最後に追加することが可能です（O(1)）。通常、再割り当てが行われると、再割り当てをあまり頻繁に行う必要がないため、メモリサイズが現時点で必要以上に増加します。

この場合、再割り当てが発生すると、平均複雑度はO(1)、最悪の複雑度はO(n)になります。