Big O?

いろいろな問題を解決する方法から何が一番いいかがわかります.コードの一般化によって名前が付けられます.

Big O Notation?

あいまいな測定定型方法.アルゴリズムに入力値が大きいほど、実行時間が長くなる関係です.トレンドだけに注目!(詳細はスキップします.)

Nの増加に伴い、計算機が実行する単純な操作数が定数に収束するf(n)より小さい場合、アルゴリズムはO(n)と呼ばれる.
f(n)=n//直線
f(n)=n^2//次関数
f(n)=1//固定値

ex)1～nの和関数
1.O(n)動作の個数はnの倍数に関係する.

function addUpTo(n){
	let total = 0;
    for(let i = 1; i <n; i++{
    		total++;}
            return total; }

2.O(1)は常に3つの操作がある

function addUpTo(n){
	return n*(n+1)/2;}
    

ex)別の例

function countUpAndDown(n){
	console.log('Going Up!");
    for(let i =0; i<n; i++){
    	console.log(i);}
    console.log('At the top! Going down...');
    for(let j = n -1; j >=0; j--){
    	console.log(j);
    console.log('Back down. Bye!');}}

いくつかのO(n)にかかわらず,トレンドが重要であるため,O(n)である.
ex)別の例-O(n^2)

function printAllPairs(n){
	for(let i =0; i<n; i++){
    	for(let j =0; j<n; j++){
        	console.log(i,j);} } }

簡略化時間複雑度BigO符号

目測規則

1.上司のことは気にしない。

O(2n) ❌ O(n) ⭕️
O(500) ❌ O(1) ⭕️
O(13n^2) ❌ O(n^2) ⭕️

2.もっと小さい単位は気にしない。

O(n + 10) ❌ O(n) ⭕️
O(100n + 50) ❌ O(n) ⭕️
O(n^2 + 2n) ❌ O(n^2) ⭕️
ex) O(n)

logALeast5(n){
	for(let i = 1; i<=Math.Max(5,n); i++){
    	console.log(i);
        }
       }

x)O(1)-5の下の数字に注意するだけで、nはどうでもいい.

logAMost5(n){
	for(let i = 1; i<=Math.Min(5,n); i++){
    	console.log(i);
        }
       }

くうかんふくざつさ

目測規則

1.ほとんどの原語(booleans、numbers、undefined、null)は定数空間である。

2.stringsはO(n)spaceです。(nは文字列の長さを表す。

3.参照タイプ(オブジェクトなど)はO(n)spaceです。(nは配列長オブジェクトにおけるキーの個数を表す。)

x)O(1)Space-nはどうでもいい.

function sum(arr){
	let total = 0; 
    for(let i = 0; i < arr.length; i++){
    	total += arr[i];}
        	return total;
            }

x)O(n)Space−arrの長さが重要である.

function double(arr){
	let newArr = []; 
    for(let i = 0; i < arr.length; i++){
    	newArr.push(2 * arr[i]);
        	return newArr;
            }

ログと色の再生

対数=>指数の反対
log2(8) = 3
log2(value) = exponent => 2^exponent = value