コーディング インタビューの Big-O 記法について簡単に説明

ウィキペディアからのこの定義は、コンピュータ サイエンスにおけるビッグ オーを、入力サイズが大きくなるにつれて実行時間またはスペースの要件がどのように増大するかによるアルゴリズムの分類としてエレガントに説明しています.

これは、入力バウンドであることを意味する漸近分析です.時間と空間に制限された入力に基づいて、アルゴリズムの最悪のシナリオを計算します.

時間と空間の計算も同様です.この説明では、時間のビッグ O 表記を計算します.

O(1)、O(log(N))、O(N)、O(N^2)の見分け方を説明します.前の文では、アルゴリズムが時間パフォーマンスの観点から整理されていることに注意してください.

たとえば、以下の特定の配列入力を使用して 3 つのアルゴリズムの時間計算量を計算します.

a = [...] where array size n

We have three algorithms that take 
array 'a' as input and returns values.

F1(a) => 1 + a[0]; 
algorithm F1 returns 1 plus the first
array value of 'a'

F2(a) => sum(a); 
algorithm F2 returns the sum of 
array value 'a'

F3(a) => pair(a); 
algorithm F3 returns the pairing of the 
array values in 'a'.
for example if a = [1,2,3], F3 returns 
1,2  
1,3  
2,1  
2,3...

配列「n」のサイズが増加した場合
10,000,000 にすると、次のことがわかります.

F1 アルゴリズムは引き続き定数で実行されます
へのポインタを参照するときの時間
array[0] のようなメモリ位置は
O(1)

F2 アルゴリズムは線形時間で実行されます.
かかる時間は比例して増加します
'n' 配列のサイズに.表現
配列サイズが入力である sum(array)
異なる場合があるのは O(N)

です

F3 アルゴリズムには、
実行されることを意味するネストされた for ループ
で O(N^2)

Big O の対数

コンピュータ サイエンスの式 log (n) = y は、対数が数学のように底が 10 ではなく底が 2 であることを前提としています.これは非常に重要な違いです.したがって、完全な式は log2 (n) = y です.

「n」を取得するには、単純に 2^y = n を実行します.つまり、log (n)=4 で 'n' を取得するには、単純に 2^4 = 16 を実行します.

O(log(N)) アルゴリズムを特定する方法
コンピュータ サイエンスでは、式 log (n) = y は log2 (n) = y に評価されることを思い出してください.log は底 2 です.したがって、式 log (n)=4 は 2^4 = 16 として解くことができ、単純に 2 を乗算します. 4 回 2*2*2*2 .

If we added 1 to 2^4+1 we would get 16*2 which is
2^5=32

これは、入力が 2 倍になったときに、もう 1 つの操作を行うだけでよいことを意味します.ここで魔法が起こります!

表記が O(log(N)) であるかどうかを理解するには、以下に示すように、二分探索のように配列を半分に切り続けるアルゴリズムがあるとします.

[0,1,2,3,4,5,6,7,8,9]
[0,1,2,3,4, | 5,6,7,8,9] => [0,1,2,3,4]
[0,1,2 | ,3,4] => [0,1,2]
[0,1 | ,2] => [0,1]
[0 | 1] => [0]

または、ツリーのデータ構造を半分にカットする場合.ツリーデータ構造 here について読んでください.これはおそらく O(log(N)) です.

さらなる研究については、https://www.algoexpert.io をご覧ください.