アルゴリズムの時間計算量の概要

コンピュータサイエンスでは、アルゴリズムの分析は非常に重要な部分です。問題を解決するための最も効率的なアルゴリズムを見つけることが重要です。問題を解決するために多くのアルゴリズムを持つことは可能ですが、ここでの課題は最も効率的なものを選択することです。

ここで重要なのは、さまざまなアルゴリズムのセットがある場合、どのようにして最も効率的なアルゴリズムを認識できるかということです。ここで、アルゴリズムの空間と時間の複雑さの概念が生まれます。空間と時間の複雑さは、アルゴリズムの測定尺度として機能します。スペース(メモリの量)と時間の複雑さ(操作の数)に基づいてアルゴリズムを比較します。

アルゴリズムが実行されるときにアルゴリズムによって使用されるコンピューターのメモリの合計量は、そのアルゴリズムのスペースの複雑さです。この記事では、スペースの複雑さについては説明しません(この記事を少し小さくするため)。

時間計算量

したがって、時間計算量は、アルゴリズムがタスクを完了するために実行する操作の数です(各操作に同じ時間がかかることを考慮して)。最小の操作数でタスクを実行するアルゴリズムは、時間の複雑さの観点から最も効率的なアルゴリズムと見なされます。ただし、スペースと時間の複雑さは、オペレーティングシステムやハードウェアなどの要因によっても影響を受けますが、この説明には含まれていません。

時間の複雑さを理解するために、特定の問題を解決するために使用される2つの異なるアルゴリズムを比較する例を取り上げます。

問題は検索です。配列内の要素を検索する必要があります(この問題では、配列が昇順でソートされていると想定します)。この問題を解決するために、2つのアルゴリズムがあります。

1.線形検索。

2.二分探索。

配列に10個の要素が含まれていて、配列内で数10を見つける必要があるとします。

const array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; const search_digit = 10;

線形検索アルゴリズムは、配列の各要素をsearch_digitと比較します配列内でsearch_digitが見つかると、trueを返します

それでは、実行する操作の数を数えましょう。ここでは、答えは10です(配列のすべての要素を比較するため)。したがって、線形検索は10個の操作を使用して、指定された要素を検索します(これらは、この配列の操作の最大数です。線形検索の場合、これはアルゴリズムの最悪のケースとしても知られています)。

一般に、線形検索は最悪の場合n回の操作を行います(nは配列のサイズです)。

この場合の二分探索アルゴリズムを調べてみましょう。

バイナリ検索は、次の例で簡単に理解できます。

出典:Learneroo

このロジックを問題に適用しようとすると、最初にsearch_digitを配列の中央の要素である5と比較します。5は10未満なので、配列要素でsearch_digitを探し始めます。目的の要素10が得られるまで、同じ方法で5より大きい。

ここで、目的の要素を見つけるためにバイナリ検索で実行された操作の数を数えてみてください。約4回の操作が必要でした。さて、これは二分探索の最悪のケースでした。これは、実行された操作の数と配列の合計サイズの間に対数関係があることを示しています。

操作数= log(10)= 4(約)

ベース2の場合

二分探索のこの結果を次のように一般化できます。

サイズnの配列の場合、二分探索によって実行される操作の数は次のとおりです。log(n)

ビッグO表記

上記のステートメントで、サイズnの配列の場合、線形検索はn回の操作を実行して検索を完了することがわかりました。一方、二分探索はlog(n)回の操作を実行しました(どちらも最悪の場合)。これをグラフとして表すことができます(x軸:要素の数、y軸:操作の数)。

出典:Techtud

図から、線形検索の複雑さが増加する速度は、バイナリ検索の場合よりもはるかに速いことが非常に明らかです。

アルゴリズムを分析するときは、時間計算量を表すために表記法を使用します。その表記法はBigO表記法です。

例:線形検索の時間計算量は、バイナリ検索のO(n)およびO(log n)として表すことができます(ここで、nおよびlog(n)は操作の数です)。

いくつかの一般的なアルゴリズムの時間計算量またはBigO表記を以下に示します。

  1. 二分探索:O(log n)
  2. 線形探索:O(n)
  3. クイックソート:O(n * log n)
  4. 選択ソート:O(n * n)
  5. 巡回セールスマン:O(n!)

結論

あなたがまだこの記事を読んでいるならば、私はあなたの努力に本当に感謝します。今、あなたは考えている必要があります-なぜ時間の複雑さを理解することがそれほど重要なのですか?

少数の要素(たとえば10)の場合、バイナリ検索と線形検索によって実行される操作の数の差はそれほど大きくないことがわかっています。しかし、現実の世界では、ほとんどの場合、大量のデータが含まれる問題に対処します。

たとえば、検索する要素が40億個ある場合、最悪の場合、線形検索ではタスクを完了するのに40億回の操作が必要になります。二分探索は、わずか32回の操作でこのタスクを完了します。それは大きな違いです。ここで、1つの操作が完了するまでに1ミリ秒かかる場合、バイナリ検索には32ミリ秒しかかからないのに対し、線形検索には40億ミリ秒(約46日)かかると仮定します。それは大きな違いです。

これが、このような大量のデータに関して、時間計算量の調査が重要になる理由です。

リソース

Grokking Algorithms-Aditya YBhargava著

BigO表記と時間計算量の概要-CSDojoによる