141

O（1）、O（n log n）、およびO（log n）の複雑さを持つ、私たちが毎日使用するいくつかのアルゴリズムは何ですか？

4

11 に答える 11

282

質問で与えられたような時間計算量のアルゴリズム/ステートメントのグループの例が必要な場合は、ここに小さなリストがあります-

O(1)時間

  • 配列インデックスへのアクセス（int a = ARR [5];）
  • リンクリストへのノードの挿入
  • スタックのプッシュとポップ
  • キューへの挿入と削除
  • 配列に格納されているツリー内のノードの親または左/右の子を見つける
  • 二重リンクリストの次/前の要素にジャンプする

O(n)時間

一言で言えば、すべてのブルートフォースアルゴリズム、または線形性を必要とするNoobアルゴリズムは、O（n）時間計算量に基づいています

  • 配列のトラバース
  • リンクリストのトラバース
  • 線形探索
  • リンクリスト内の特定の要素の削除（ソートされていません）
  • 2つの文字列を比較する
  • 回文のチェック
  • カウント/バケットソートそしてここでもそのような例を100万以上見つけることができます...

O(log n)時間

  • 二分探索
  • 二分探索木で最大/最小の数を見つける
  • 線形機能に基づく特定の分割統治アルゴリズム
  • フィボナッチ数の計算-最良の方法ここでの基本的な前提は、完全なデータを使用せず、反復ごとに問題のサイズを減らすことです。

O(n log n)時間

'log n'の係数は、分割統治法を考慮して導入されます。これらのアルゴリズムのいくつかは、最適化されたものであり、頻繁に使用されます。

  • マージソート
  • ヒープソート
  • クイックソート
  • O（n ^ 2）アルゴリズムの最適化に基づく特定の分割統治アルゴリズム

O(n^2)時間

これらのアルゴリズムは、対応するO（nlogn）が存在する場合、効率の低いアルゴリズムであると考えられます。一般的なアプリケーションは、ここではブルートフォースです。

  • バブルソート
  • 挿入ソート
  • 選択ソート
  • 単純な2D配列のトラバース
于 2012-07-23T11:37:22.267 に答える
34

O（1）-ほとんどの調理手順はO（1）です。つまり、調理する人が増えても一定の時間がかかります（ある程度、鍋/鍋のスペースが不足する可能性があるため）と料理を分割する必要があります）

O（logn）-電話帳で何かを見つけます。二分探索を考えてください。

O（n）-本を読む。nはページ数です。これは、本を読むのにかかる最小時間です。

O（nlogn）-マージまたはクイックソートを使用してカードをソートしない限り、nlognである毎日行う可能性のあることをすぐに考えることはできません！

于 2009-10-20T05:57:25.570 に答える
30

の簡単な例は次のO(1)ようになりますreturn 23;-入力が何であれ、これは固定された有限の時間で返されます。

の典型的な例はO(N log N)、適切なアルゴリズム（マージソートなど）を使用して入力配列をソートすることです。

O(log N)ソートされた入力配列の値を二等分で検索する場合の典型的な例。

于 2009-10-20T05:43:24.450 に答える
10

私はあなたにいくつかの一般的なアルゴリズムを提供することができます...

  • O（1）：配列内の要素へのアクセス（つまり、int i = a [9]）
  • O（n log n）：クイックまたはマージソート（平均）
  • O（log n）：二分探索

これは宿題/インタビューのような質問のように聞こえるので、これらは腸の反応になります。より具体的なものを探している場合、一般の人々は人気のあるアプリケーションの基礎となる実装（もちろんオープンソースを節約する）を知らないため、少し難しいです。また、概念は一般に「アプリケーション」にも適用されません。

于 2009-10-20T05:43:12.157 に答える
4

O（1）：チェスで次の最良の動きを見つける（またはそのことについては行く）。ゲームの状態の数は有限であるため、O（1）のみです:-)

于 2009-10-20T05:50:33.620 に答える
3

O（1）-二重リンクリストから要素を削除します。例えば

typedef struct _node {
    struct _node *next;
    struct _node *prev;
    int data;
} node;


void delete(node **head, node *to_delete)
{
    .
    .
    .
}
于 2009-10-20T09:13:13.460 に答える
2

ソフトウェアアプリケーションの複雑さは測定されておらず、big-O表記で書かれていません。アルゴリズムの複雑さを測定し、同じドメイン内のアルゴリズムを比較することだけが役立ちます。ほとんどの場合、O（n）とは、「O（n）比較」または「O（n）算術演算」を意味します。つまり、アルゴリズムやアプリケーションのペアを比較することはできません。

于 2009-10-20T05:40:44.580 に答える
2

次のアルゴリズムをリストに追加できます。

O(1)-数値が偶数か奇数かを判断する。HashMapの操作

O(logN)-x ^ Nの計算、

O(N Log N)-最長増加部分列

于 2009-10-20T07:01:44.417 に答える
1

O（n log n）は、任意のセットをソートできる速度の上限として有名です（標準であり、高度に並列化されていないコンピューティングモデルを想定しています）。

于 2009-10-20T05:47:21.597 に答える
0

0（logn）-バイナリ検索、配列内のピーク要素（複数のピークが存在する可能性があります）0（1）-Pythonでリストまたは文字列の長さを計算します。len（）関数は0（1）時間かかります。配列内の要素へのアクセスには0（1）時間がかかります。スタックでのプッシュ操作には0（1）時間がかかります。0（nlogn）-マージソート。Pythonでの並べ替えにはnlogn時間がかかります。したがって、listname.sort（）を使用すると、nlogn時間がかかります。

注–ハッシュテーブルでの検索は、衝突のために一定時間以上かかる場合があります。

于 2018-10-17T13:36:37.343 に答える
0

O（2 N）

O（2 N）は、入力データセットへの追加ごとに成長が2倍になるアルゴリズムを示します。O（2 N）関数の成長曲線は指数関数的です-非常に浅いところから始まり、その後、気象的に上昇します。O（2 N）関数の例は、フィボナッチ数の再帰計算です。

int Fibonacci (int number)
{
if (number <= 1) return number;
return Fibonacci(number - 2) + Fibonacci(number - 1);
}
于 2018-10-29T15:38:13.037 に答える