BigO表記の初心者向けガイド

Big O表記法は、アルゴリズムの実行にかかる時間を表す方法です。これにより、ソフトウェアエンジニアは、問題を解決するためのさまざまなアプローチがどれほど効率的であるかを判断できます。

Big ONotationの時間計算量の一般的なタイプを次に示します。

  • O(1)-一定の時間計算量
  • O(n)-線形時間計算量
  • O(log n)-対数時間計算量
  • O(n ^ 2)-2次時間計算量

この記事の終わりまでに、Big ONotationの基本を理解できるようになることを願っています。

O(1)—一定時間

一定時間アルゴリズムは、実行に常に同じ時間がかかります。これらのアルゴリズムの実行時間は、入力のサイズとは無関係です。O(1)時間の良い例は、配列インデックスを使用して値にアクセスすることです。

var arr = [ 1,2,3,4,5];
arr[2]; // => 3

その他の例としては、配列に対するpush()およびpop()操作があります。

O(n)-線形時間計算量

アルゴリズムを実行する時間が入力サイズnに正比例する場合、アルゴリズムの時間計算量は線形になります。したがって、アルゴリズムの実行にかかる時間は、入力nのサイズが大きくなるにつれて比例して長くなります。

良い例は、CDのスタックからCDを見つけたり、本を読んだりすることです。ここで、nはページ数です。

O(n)の例は、線形探索を使用しています。

//if we used for loop to print out the values of the arrays
for (var i = 0; i < array.length; i++) { console.log(array[i]);}
var arr1 = [orange, apple, banana, lemon]; //=> 4 steps
var arr2 = [apple, htc,samsung, sony, motorola]; //=> 5 steps

O(log n)-対数時間計算量

アルゴリズムの実行にかかる時間が入力サイズnの対数に比例する場合、アルゴリズムの時間計算量は対数になります。例として、データセットの検索によく使用されるバイナリ検索があります。

//Binary search implementationvar doSearch = function(array, targetValue) { var minIndex = 0; var maxIndex = array.length - 1; var currentIndex; var currentElement; while (minIndex <= maxIndex) { currentIndex = (minIndex + maxIndex) / 2 | 0; currentElement = array[currentIndex]; if (currentElement  targetValue) { maxIndex = currentIndex - 1; } else { return currentIndex; } } return -1; //If the index of the element is not found.};
var numbers = [11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33];
doSearch(numbers, 23) //=>; 6

対数時間計算量の他の例は次のとおりです。

Example 1;
for (var i = 1; i < n; i = i * 2) console.log(i);}
Example 2;
for (i = n; i >= 1; i = i/2) console.log(i);}

O(n ^ 2)-2次時間計算量

実行までの時間が入力サイズの2乗に比例する場合、アルゴリズムの時間計算量は2次式になります。この良い例は、カードのデッキに重複があるかどうかを確認することです。

ネストされたforループなど、ネストされた反復を含むアルゴリズムでは、2次の時間計算量に遭遇します。実際、ネストされたループが深くなると、O(n ^ 3)、O(n ^ 4)などになります。

for(var i = 0; i < length; i++) { //has O(n) time complexity for(var j = 0; j < length; j++) { //has O(n^2) time complexity // More loops? }}

二次時間計算量の他の例には、バブルソート、選択ソート、挿入ソートが含まれます。

この記事は、Big ONotationの表面をかじっただけです。Big O表記について詳しく知りたい場合は、Big-Oチートシートを確認することをお勧めします。