アルゴリズムの複雑さ

2021-08-03T18:40:00.000Z

Jan Barášek

Obsah článku

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

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

ビッグオー記法

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

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

| アルゴリズム名｜ベスト｜アベレージ｜ワースト｜メモリー｜安定性｜コメント｜(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 - 最長のキーの長さ｜です。

Jan Barášek Více o autorovi

Autor článku pracuje jako seniorní vývojář a software architekt v Praze. Navrhuje a spravuje velké webové aplikace, které znáte a používáte. Od roku 2009 nabral bohaté zkušenosti, které tímto webem předává dál.

Rád vám pomůžu: