O（1）、O（n log n）、O（log n）の複雑さを持つアルゴリズムの例

Question

毎日O log n）複雑さ？

Answer 1

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

O（1）時間
1.配列のインデックス（int型へのアクセス= ARR [5];リンクリスト内のノード
3.親またはの右/左の子を見つけるキュー
5から挿抜4. スタック
上を押すとPopingの挿入）
2配列
に格納されたツリー内のノード横断配列
2を横断二重連結リスト
、あなたは万の以上のこのような例を見つけることができます...

O（n）の時間
1次/前の要素へ6.ジャンプ回文
7カウント/バケツソート
の確認二つの文字列
6を比較すると、リンクされたリスト内の特定の要素のリンクリスト
3.リニア検索
4.削除（ソートされていない）
5.とここでもあなたは万の以上のこのような例を見つけることができます....一言で言えば
、すべてのブルートフォースアルゴリズム、または直線性を必要とNoobのものは、（O（n）の時間複雑

Oをに基づいていますベストの方法
- フィボナッチ数の計算リニア機能
4に基づいて、二分探索木
3.特定の分割統治アルゴリズムで最大/最小の番号を見つけるのバイナリ検索
2に
1. n）の時間を記録しますここでの基本的な前提は完全なデータを使用せず、すべての反復で問題のサイズを小さくすることです

O（nlogn）時間
1マージソート
2.ヒープソート
3クイックソート
4 Oの最適化に基づいて、特定の分割統治アルゴリズム（N^2）のアルゴリズム
因子分裂と征服を考慮して 'log n'の導入を紹介します。これらのアルゴリズムの中には、最適化されたものがあり、頻繁に使用されるものもあります。

はO（n^2）の時間
1バブルソート
2.挿入ソート
3。選択ソート
4.単純な2D配列の移動
これらのオブジェクトは、O（nlogn）対応オブジェクトが存在する場合、効率の低いアルゴリズムと思われます。一般的なアプリケーションはここでブルートフォースかもしれません。

これがあなたの質問にうまく答えることを願っています。ユーザーが追加する例があれば、私はもっと幸せになります:)

Answer 2

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

Answer 3

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

• O（1）：配列の要素にアクセスする（つまり、iは= INT [9]）
• O
（N Nログ） ：迅速またはマージソート（平均して）
• O（n個のログを記録）：この質問の宿題/インタビュー一種のように聞こえるようバイナリ検索

これらは、腸の応答になります。もっと一般的なアプリケーションの基本的な実装（オープンソースの確保）や、一般的な概念は「アプリケーション」

には適用されないので、より具体的なものを探しているなら、少し難しいでしょう。

Answer 4

O(1)の簡単な例はreturn 23;であるかもしれません - 入力が何であれ、これは固定された有限の時間に戻ります。

O(N log N)の典型的な例は、良いアルゴリズム（例えば、mergesort）で入力配列をソートすることです。

O(log N)が2等分してソートされた入力配列の値を参照する場合の典型的な例です。

Answer 5

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

Answer 6

O（1）：Chessの中で次の最良の動きを見つける（またはその点についてはGoを参照）。

Answer 7

O（1） - ほとんどの調理手順はO（1）であり、それ以上の場合でも一定の時間がかかりますあなたの鍋/鍋のスペースが足りなくなり、料理を分けなければならないので、料理する人もいます。

O（ログ） - あなたの電話帳に何かを見つける。バイナリ検索を考えてください。

O（n） - 本を読む。nはページ数です。それは、本を読むのに最低限必要な時間です。

O（nlogn） - あなたがマージまたはクイックソートを行うことでカードをソートしない限り、nlognである毎日何かをすることはできません。

Answer 8

あなたはあなたのリストに次のアルゴリズムを追加することができます。

O(1) - 数が偶数か奇数であるかどうかを決定します。コンピューティングX^N、

O(N Log N) - - ハッシュマップ

O(logN)で作業最長増加サブ

Answer 9

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

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


void delete(node **head, node *to_delete) 
{ 
    . 
    . 
    . 
}