アルゴリズムの複雑さ

各アルゴリズムにはそれぞれ複雑さがあり、数学的な表記で表すことができる。この概要では、入力データのサイズ（扱う要素の数）に応じてアルゴリズムの典型的な複雑さを示し、どのタイプのアルゴリズムがどのタイプのタスクに適しているかを示しています。

一般に、問題の種類ごとに最適な特化型アルゴリズムが存在する。どのアルゴリズムも万能ではなく、常に自分の文脈を知る必要があります。

ビッグオー記法

Big O記法*は、入力サイズが大きくなるにつれて、実行時間またはメモリ要件がどのように増加するかによってアルゴリズムを分類するために使用されます。

次の表は、Big O記法で指定されたアルゴリズムで最も一般的な成長順序を示しています。

以下は、最もよく使われるBig Oの表記法のリストと、異なる入力データサイズに対する性能の比較である。

| ビッグオー表記｜要素数10の場合の複雑さ｜要素数100の場合の複雑さ｜要素数1000の場合の複雑さ | -------------- | ---------------------------- | ----------------------------- | ------------------------------- | | O(1) | 1 | 1 | 1 | | O(log N)｜3｜6｜9｜｜｜｜。 | o(n)｜10｜100｜1000｜｜。 | O(N log N)｜30｜600｜9000｜です。 | o(n^2)｜ 100｜10000｜1000000｜です。 | O(2^N)｜1024｜1.26e+29｜1.07e+301｜1.07e+301 | O(N!) | 3628800 | 9.3e+157 | 4.02e+2567 **。

データ構造操作の複雑さ

| データ構造｜アクセス｜検索｜挿入｜削除｜コメント｜｜｜etc. | ----------------------- | :-------: | :-------: | :-------: | :-------: | :-------- |

| スタック｜n｜n｜1｜1｜1｜1｜1｜1｜1

| リンクリスト｜n｜n｜1｜n｜｜｜｜。 | ハッシュテーブル｜ -｜ n｜ n｜ n｜ n｜完全なハッシュ関数の場合、複雑さはO(1)になります｜。 | 二分探索木｜n｜n｜n｜n｜バランス木の場合、計算量はO（log（n））｜。 | B-Tree｜log(n)｜log(n)｜log(n)｜log(n)｜log(n) | 赤黒木｜log(n)｜log(n)｜log(n)｜log(n)｜log(n) | AVLツリー｜log(n)｜log(n)｜log(n)｜log(n)｜log(n) | ブルームフィルタ | - | 1 | 1 | - | 偽陽性を検索するとき

ソーティングアルゴリズムの複雑さ

| アルゴリズム名｜ベスト｜アベレージ｜ワースト｜メモリー｜安定性｜コメント｜(1) | --------------------- | :-------------: | :-----------------: | :-----------------: | :-------: | :-------: | :-------- | | バブルソート｜n｜n²｜n²｜1｜はい｜｜｜です。 | 挿入ソート｜n｜n²｜n²｜1｜｜｜｜｜｜｜｜｜。 | 選択ソート｜n²｜n²｜n²｜1｜｜｜｜｜｜｜｜｜｜｜｜｜。 | ヒープソート**｜ n log(n) | n log(n) | n log(n) | 1｜いいえ｜｜｜｜です。 | マージソート｜ n log(n) | n log(n) | n log(n) | yes｜｜｜｜｜. | クイックソート｜ n log(n) | n log(n) | n² | log(n) | いいえ｜クイックソートは通常O（log（n））のスタック計算量で実行されます。 | シェルソート | n log(n) | 配列に依存する | n (log(n))² | 1 | ない |｜｜｜｜｜｜。 | 数え上げソート｜ n + r｜n+r｜n+r｜n+r｜はい｜r - 配列の中で最大の数｜です。 | ラディックスソート｜ n * k｜nk｜nk｜n+k｜はい｜k - 最長のキーの長さ｜です。