o(log n)は何ですか?ビッグO対数時間複雑性を学ぶ

コンピュータサイエンスの話題は大きいO表記より恐ろしいですか?名前を怖がらせないでください、大きなO表記法は大したことではありません.それは非常に理解しやすいですし、そうするために数学whizする必要はありません.このチュートリアルでは、JavaScriptの例でビッグO対数時間の複雑さの基礎を学びます.
これはビッグO表記のシリーズの第4です.あなたがループにとどまりたいならば.sign up for my weekly newsletter, The Solution .

どのような問題は、大きなOを解決するのですか?

ビッグO表記法は、我々は質問に答えることができます

ビッグO表記法は、他の開発者(および数学者!)とのパフォーマンスを議論するための共有言語を備えています!

クイックリフレッシュ
あなたがちょうど我々に加わっているならば、あなたはその記事から始めたいです.What is Big O Notation?

何が大きいOですか?
ビッグO表記法は、アルゴリズムの成長率を測定するためのシステムです.大きいO表記法は、時間と空間に関してアルゴリズムの複雑さを数学的に説明します.我々は数秒(または分!)のアルゴリズムの速度を測定しないでください.代わりに、我々が完了するためにかかる操作の数を測定します.
oは「順序」に対して短い.ですから、O(log n)を使ってアルゴリズムを議論しているのであれば、その成長順序や成長率は「log n」や対数複雑さだと言います.

どのように、大きいOは働きますか?
ビッグO表記法は最悪ケースのシナリオを測定します.
なぜ?
何故なら我々は知らない.
他の解決策を評価できるように、我々のアルゴリズムがどれほど不十分かを知る必要がある.
最悪のシナリオはまた、上限として知られています.我々が上限を言うとき、我々はアルゴリズムによって実行される操作の最大数を意味します.
このテーブルを覚えていますか.
O
複雑さ
成長率
o ( 1 )
定数
ファースト
o ( log n )
対数
o ( n )
線形時間
o ( n * log n )
ログ線形
o ( n ^ 2 )
二次
o ( n ^ 3 )
キュービック
o ( 2 ^ n )
指数関数
o ( n !)
要因
スロー
これは、最速から低速に成長率によって共通の順序を示します.
我々は、(1)、または定数時間の複雑さを学んだWhat is Big O? , o ( n ) inBig O Linear Time Complexity , とo ( n ^ 2 )Big O Quadratic Time Complexity .
o(n ^ 2),2次時間の複雑さを学習した後に理解するのが容易であるので,我々は以前にo(log n),対数複雑性をスキップした.
今では時間です!

数学時🧮 🕝
対数は何ですか.
Logarithms 電源をリバースエンジニアに許可します.( Kryptoniteのように).これらは指数関数の逆演算である.
対数を指数関数の逆操作と考えることができる.標準化テストからこの類推形式を覚えていますか?

A is to B as X is to Y.

私たちは言うことができる、“加算は、指数化が対数にあるように減算することです.”
また、「指数化は対数による除算である.」
二次時間計算量でn＊nはn ^ 2であることを示した.
nの値が2の場合、n ^ 2は4に等しい.
次に、2〜3番目のパワー、2 ^ 3が8に等しいことになる.
"long "形式では以下のようになります.

2 * 2 * 2  = 8

どうすればこの問題を与えられたか?

2^y = 8

この問題をどう説明しますか.
私たちは、「私たちは8の製品のために2を上げますか?」
🧐
我々はまた、“どのように多くの2つの我々は8を得るために一緒に乗算する必要がありますか?”
式の記法は以下の通りです.

log2(8) = y

どこ2 がベースです.8 は引数とy は指数です.
なぜです8 議論(何をしたか)
log 2 ()は関数ですから!
🤯
「2のベース2の対数は3である」として製品を記述できました
基地で何を意味するか
“In exponentiation, the base is the number b in an expression of the form b^n.”
対数に関する3つの最も一般的なベースは以下の通りです.

2

10

エ

デジタル電子工学とコンピューターサイエンスでは、我々は(ほとんど常に)Base - 2を使います、あるいはbinary numeral system .
base 2では0と1の2つのシンボルを数えます.
よく見る?
それはブールです!👻
を返します.decimal numeral system .

10^2 = 100
10^3 = 1000
etc.

あなたが本当にオタクアウトしたいならば、あなたはEEuler’s constant : 自然対数が1に等しい一意の数.
☝️ 対数は平方根ではない.
8の平方根は2.82842712475である.
8のlog 2は3である.
ここで小さな違いが、我々の引数が増加した場合?
2048年の平方根は45.2548339959です.
2048年のlog 2は11である.
我々が対数をグラフにするか?

空力!
我々が対数時間複雑さを他の時間複雑度に比較するならばubiquitous Big O cheat sheet , 何を見ますか.

私たちが見ることができるように、対数時間の複雑さは非常に良いです!
どのような問題は、“どのように多くの3 s、一緒に乗算、8を得るために取るか?”
答えは1.8927892607です
あなたが手でその数を計算して想像するならば、退屈なプロセスです、あなたは正しいでしょう.
そういうわけで我々は発明したslide rulers とファンシー電卓.
ラッキー私たちのために、我々は機能の正確なログを計算する必要はありません.
大きいOで、我々は詳細を離れて要約します.
我々は、我々のアルゴリズムの特定の実装に関係していません.
我々はアルゴリズムの順序に興味を持っているので、代替解を比較し評価することができます.
私たちはログの定数を一定としますので、以下のように表記します.

O(log n)

o ( log n ):バイナリ検索
o(log n)を説明するのに使用される古典的な例はバイナリ検索です.二項探索は、入力を各反復で半分に分割することによって、ソートされた一連の引数の位置を見つけるアルゴリズムです.
次の配列を指定し、番号の位置を求めてみましょう512 :

const powers = [1, 2, 4, 8 ,16, 32, 64, 128, 256, 512];

まず、この問題に対するブルートフォース解をレビューしましょう.

const bruteSearch = (arr, num) => {

   for (let i = 0; i < arr.length; i++) {
       if (arr[i] === num) {
           return `Found ${num} at ${i}`;
       }
   }
}

の値をマップしましょうi and arr[i] 配列で、J 4 F :
私
ARR [ I ]
0
1
1
2
2
4
3
8
4
16
5
32
6
64
7
128
8
256
9
512
何の大きなOのbruteSearch() ?
o ( n )
見つけるnum , 我々は、配列のすべての項目をチェックする必要があるので、時間の複雑さは線形です.
我々はより良いか?
確かに.
何がこの機能で起こっている?

const powers = [1, 2, 4, 8 ,16, 32, 64, 128, 256, 512];

const binarySearch = (arr, num) => {

   let startIndex = 0;
   let endIndex = (arr.length)-1;

   while (startIndex <= endIndex){

       let pivot = Math.floor((startIndex + endIndex)/2);

       if (arr[pivot] === num){
            return `Found ${num} at ${pivot}`;
       } else if (arr[pivot] < num){
           startIndex = pivot + 1;
       } else {
           endIndex = pivot - 1;
       }
   }
   return false;
}

我々の最初の反復でwhile ループは、我々の配列の中央にピボットを作成します.その後チェックnum を返します.pivot .
If pivot はnum , 帰ります.
If pivot がnum , 我々は、我々の価値を変えますstartIndex 我々の価値にpivot プラスワン.
なぜ?
値arr[pivot] がnum , 我々は以下のいずれかの要素をチェックする必要はありませんpivot を返します.
我々は、ちょうど我々の入力を半分にしました!
n/2
If pivot がnum , 我々は、我々の価値を変えますendIndex 我々の価値にpivot マイナスワン.
値array[pivot] がnum , 我々は、上記のいずれかの要素をチェックする必要はありませんpivot を返します.
次の反復では、新しいpivot 調整中の中央値startIndex and endIndex , そして再びarr[pivot] に対してnum .
上の例では、入力を再び半分にします.
半分の半分ですか.
四半期.
n/4
番目の繰り返しでは、入力を再び半分にします.
最終的な反復では、我々の数を見つけます.その時点では何も残っていない.
どのようなパターンですか?
テーブルを作りましょう!
startindex
Endindex
ピボット
エレメント
n
0
9
4
10
n
5
9
7
5
n/2
8
9
8
2
n/4
9
9
9
1
N/8
どのような要素の列の列についてはどのように注意してください?
我々は、ゼロに達するまで、2つで、多かれ少なかれ、それを分割します.
n列のシーケンスについてはどのように気付きますか?
2
4
8
2つの力!
入力を各反復で分割することにより指数を反転させる.
📝 入力が各反復で分割されるこのパターンを見ると、O(log n)です.

大きいO対数時間複雑さ
o(log n)スケール?
確かに.
このチュートリアルでは、JavaScriptの例を使用して、大きなO対数の複雑さの基礎を学びました.私たちがO(n log n)を見る大きいO記法の上でこのシリーズのパート5のために調整されるか、線形時間複雑性を記録してください.あなたがループにとどまりたいならば.sign up for my weekly newsletter, The Solution .