03. 알고리즘 수행 시간 [1 2주차]

3. 알고리즘 수행 시간 [1-2주차]

2024년 1월 9일 화요일

오후 10:59

<점근적 표기>

1. O : 점근적 상한

O(g(n)) = {f(n) | 충분히 큰 모든 n에 대하여 f(n)<=c*g(n)인 양의 상수 c가 존재}

ex) {3n², n²+n+3, n+2, nlogn, 3} ⊂ O(n²)

2. Ω : 점근적 하한

Ω(g(n)) = {f(n) | 충분히 큰 모든 n에 대하여 c*g(n)<=f(n)인 양의 상수 c가 존재}

ex) {n³, n²+3, 3n+2} ⊂ Ω(n)

3. Θ

Θ(g(n)) = O(g(n)) ∩ Ω(g(n))

= {f(n) | 충분히 큰 모든 n에 대하여 c₁*g(n)<=f(n)<=c₂*g(n)인 양의 상수 c₁, c₂가 존재}

ex) {n²+n+3, 2n²+3} ⊂ Θ(n²)

<수행 시간>

일반적으로 입력 크기가 커질수록 알고리즘의 수행시간이 증가하므로, 수행시간을 입력 크기의 함수로 표현한다.

또한, 코드의 각 행을 실행하는 데 상수 시간이 걸린다고 가정한다.

삽입 정렬의 수행 시간을 계산하면 다음과 같다.

• 삽입 정렬의 수행시간은 O(n²).

최선의 경우 Θ(n), 최악의 경우 Θ(n²)

<시간복잡도에서 log>

시간복잡도에서 로그의 밑 2가 생략되는 경우가 많음.

k = logn ó 2^k = n

따라서 logn은…

    - 2를 몇 번 곱하면 n이 되느냐의 질문에 대한 답

    - n을 2로 몇 번 나누면 1이 되느냐의 질문에 대한 답

로그함수는 지수함수의 역함수

이를 이용해 이진 탐색(재귀)의 시간복잡도를 구할 수 있다.

T(n) = 1+T(n/2) = 1+1+T(n/4)= …

= T(2^logn) = 1+T(2^logn-1) = 1+1+T(2^logn-2) = ... = logn

∴T(n)=O(logn)

logn은 n보다 월등히 작다

    - logn=10, n=1024