2つのアルゴリズムの複雑さを比較する：両方のアルゴリズムに適用可能な基本操作を識別しますか？

Question

私は理論的に2つのアルゴリズム（ソート）の複雑さを分析してそれらを比較する必要があります。それから私はそれらを実装し、経験的に効率を確認しようとします。

私は両方のアルゴリズムを分析しましたが、私は効率クラスを知っていますが、基本的な操作を特定するのに問題があります。両方のアルゴリズムに適用できるはずなので、基本的な操作を選択する際に注意する必要があるというヒントがありました。私の問題は、なぜ私が両方のアルゴリズムで同じ基本操作を取るべきかわからないということです。

擬似コード

Algo1：

//sorts given array A[0..n-1] 
for i=0 to n-2 
    min <- i 
    for j <- i+1 to n-1 
    if A[j] < A[min] min <- j 
    swap A[i] and A[min] 

効率：シータ（N^2）

Algo2：

//sorts given array with limited range (u,l) 
for j = 0 to u-l D[j] = 0 
for i = 0 to n-1 
    D[A[i]-l] = D[A[i]-l]+1 
for j=1 to u-l D[j] = D[j-1]+D[j] 

for i=n-1 to 0 
    j = A[i]-l 
    S[D[j]-1] = A[i] 
    D[j] = D[j]-1 
return S 

効率Levitin - >シータ（N）、Johnsonbaugh - >シータ（n + m）m：配列内の異なる整数

基本的な操作として最も頻繁に発生する操作を選択し、各アルゴリズムごとに異なる基本操作を選択すると、違いがある理由がわかりません。最終的には、同じ効率クラスにつながるため、経験的分析（異なる入力サイズに必要な基本的な操作の数を比較する）にとって重要であるため、問題はありませんか？

ここでは、Algo1では5回、Algo2では6回（もちろんループに依存して）実行される基本操作として割り当てを選択します。このアプローチには欠点がありますか？

Answer 1

「基本操作」の一般的な選択肢は、比較数またはスワップ数を調べることです。

「ホット」アイテムがキャッシュにあり、「コールド」アイテムがL2ミスに続いてRAM参照、またはディスクI/Oとなるメモリ階層を持つシステムを考えてみます。次に、キャッシュヒットコストは本質的にゼロであり、基本的な動作はキャッシュミスのコストになり、時間の複雑さのための新しい表現につながる。

ほとんどの注文リストはmore often than you might thinkにソートされています。安定したソートは、不安定なソートよりもキャッシュに優しい可能性があります。ソートの比較順序がキャッシュの追い出しとどのようにやりとりするかについて簡単に判断できる場合、期待される実行時間についての良い説明が得られる可能性があります。

EDIT： "A []"の要素を読み上げることは、公正な操作であるようです。愛好家の分析は、「キャッシュミスがA []」に何回発生するかを調べます。