この記事はnaver boostcourseです
『コンピュータサイエンス』(CS 50)コースのまとめです.
前のWEEK 1,2,3は基礎文法です.
WEEK 4から整理開始

0.入る前に

アルゴリズムとは?

入力によって出力を抽出する方法です.
(電子工学部はシステムと呼ぶ可能性がある)
アルゴリズム#アルゴリズム#
いかなる問題を解決するために制定された一連のプログラムまたは方法を式化して表現する.
良いアルゴリズムを作成したいなら
私たちはまだ余分なことを考えなければなりません.
「効率性」です.
効率は2つの基準で測定できる.
1.空間複雑度(空間複雑度)
2.時間複雑度(時間複雑度)
このレッスンでは、アルゴリズム
かかる時間を基準に「時間の複雑さ」を説明します.

1.検索アルゴリズム

上のようなロッカーでは、ランダム1,2,3,4,5,6,7,50
中にあると想像して、50を探しています.

から順に検索します.(線形検索、線形検索)

の中央から探し始め、50未満であれば左側50より大きく、右へ行きます.(バイナリ検索)

以上の2つの方法があるはずです.
さらに、医師のコードで書いてみます.

線形探索

For i from 0 to n-1 // 처음 locker에서부터 끝까지 반복한다.

	if i'th element is 50  //만약 50을 찾았다면
    	return true        //true 
        
return false	//못찾았다면 false
    

バイナリ検索

if no items  // 어디에도 50이 없다면 false

	return false
    
if middle item is 50  // 중간을 찾았는데 50이 나왔다면?

	return true  //true
    
else if 50 < middle item  //중간을 찾았는데 50보다 크다면

	search left half  // 왼쪽으로간다.
    
else if 50 > middle item  // 중간을 찾았는데 50보다 작다면?

	search right half  // 오른쪽으로 간다.

もちろん、バイナリ検索を使用するには、ソートされた配列(または無効)が必要です.

2. 알고리즘 표기법

良いアルゴリズムは効率的でなければならない.
アルゴリズムはどんなによく設計されているか.
時間複雑度(time complexity)で基準を定義します.
時間の複雑さはまた3つに分けられる.

big-Oマーキング法
->ここでOは「on the order of」の略で、「~まで大きくなる」という意味です.(運転時間上限)

メガバイト
->実行時間の下限.

ビセタ符号法

上のロッカーで50を探す過程を線形検索と考えます.
0番(コンピューターエンジニアなので)ロッカーからn-1番ロッカーまで
最悪の場合、全部でn回確認します.(50が最後かもしれないので)
上の赤いグラフが描かれています.
では、バイナリ検索の状況はどうなりますか?log2n{log{2}n}log2n.
ナビゲーションするサイズがnだと思う場合は、プロセスを考慮してください.

は真ん中を探索している.

のサイズを判別します.(条件文)

方向が確定すると残りの半分(n 2frac{n}{2}2 n)

が破棄される.

を繰り返し実施すると、半分は廃棄される.(n2\frac{n}{2}2n​ x 12\frac{1}{2}21​ ...)

k回繰り返すと、(n 2)k=1(frac{n}{2})^k=1(2 n)k=1
(存在する場合はfalsereturn)
計算超過量であれば、k=log 2 n{k=log 2}n}k=log 2 n
上図に緑のグラフがあります.
上記の2つの状況は最悪だと仮定します.
私は本当に運が悪くて、探してまた探して、最後に
存在する場合です.
この場合,時間複雑度ではbigoマーキング法でマーキングする.
時間の複雑さは正確に数値化するのにどれくらいの時間がかかるかの表現ではない.
私たちが日常生活の中で「それは多分こんなに大きいでしょう?」君が言ったように
これは大体の時間要素をマークする方法です.
状況が大きすぎると仮定する
n{n}n , n2\frac{n}{2}2n​, n3\frac{n}{3}3n​ .. すべてnnnです.
log 2 nlog{2}nlog 2 nも同様である.lognlognlognとマークします.
逆に時間の下限を考えると
線形検索は一度に見つかるはずです.
運がよかったので、ロッカーを開けると50がありました.
バイナリ検索も一度に見つけることができます.
考えてみれば、ビオミカが1ではない可能性はありますか?
あります.アルゴリズムがロッカーの数を数える必要がある場合は、いくら良くてもn個数えます.
Big−OおよびBig−OmegaではBig−Oがより重要である.
なぜなら、ソート後の値を再高速にソートするのは良いアルゴリズムですか?
把握しにくいからです.