0

comフォーラム、

以下のアルゴリズムを C++ でコンパイルしようとしています。アイデアはありますか?

// Find the distance between the two closest elements in an array of numbers.
// Minimum Distance
// dmin = infinity;
// for i = (i to n - 2) do
// for j = i + 1 to n - 1 do
// temp = A[i] - A[j]
// if temp < dmin;
// dmin = temp;
// return dmin;
4

2 に答える 2

1

O(n^2)そのアルゴリズムを使用するのではなく ( )、数値を並べ替えてから線形スキャンを実行することをお勧めします( O(nlogn))。

于 2012-06-10T11:27:22.803 に答える
0

はい、phant0m は正しいですが、並べ替えアルゴリズム自体はサイクルを使用します。

ソートアルゴリズムは通常、その効率によって判断されます。この場合、効率とは、入力のサイズが大きくなったときのアルゴリズムの効率を指し、通常、並べ替える要素の数に基づいています。使用されているほとんどのアルゴリズムのアルゴリズム効率は、O(n^2) または O(n*log(n)) です。(http://www.cprogramming.com/tutorial/computersciencetheory/sortcomp.html)

配列がすでにいくらか順序付けられているか、後でソートされたバージョンが必要になるか、配列が非常に大きくなる可能性がある場合を除き、「弾丸を噛んで」元のアプローチに固執することもできます。

于 2012-06-10T12:31:49.060 に答える