質問

私たちが日常的に使っているアルゴリズムで、O(1)、O(n log n)、O(log n)の複雑さを持つものは何でしょうか？

どのように解決するのですか？

あなたが質問に与えられたような時間の複雑さを持つアルゴリズム/ステートメントのグループの例をしたい場合は、ここで小さなリストです - 。

O(1) 時間

• 配列のインデックスにアクセスする (int a = ARR[5];)
• リンクリストへのノードの挿入
• スタックへのプッシュとポッピング
• キューへの挿入と削除
• Arrayに格納されたツリーのノードの親や左子・右子の検索
• 二重リンクリストの次/前の要素へのジャンプ

O(n) 時間

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

• 配列のトラバース
• リンクリストの走査
• 線形探索
• リンクリストの特定要素の削除 (ソートされていない)
• 2つの文字列を比較する
• 回文かどうかのチェック
• カウント/バケットソート などなど、このような例は他にもたくさんあります。

O(log n) 時間

• バイナリサーチ
• 二項探索木における最大/最小の数を求める。
• 線形関数に基づく特定の分割統治アルゴリズム
• フィボナッチ数の計算 - 最適な方法 基本的な前提は、完全なデータを使用しないこと、そして、反復するごとに問題サイズを小さくすることです。

O(n log n) 時間

log n'のファクターは、Divide and Conquerを考慮することで導入されています。これらのアルゴリズムの中には、最適化されたものがあり、頻繁に使用されています。

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

O(n^2) 時間

これらは、O(nlogn)の対応するものが存在する場合、効率の悪いアルゴリズムであると思われます。一般的なアプリケーションは、ここでBrute Forceになるかもしれません。

• バブルソート
• 挿入ソート
• 選択ソート
• 単純な2次元配列のトラバース