목차

1. 인트로
2. O($\log n$) 알고리즘
3. O($\sqrt{n}$) 알고리즘
4. O(n) 알고리즘
5. O($n^2\log n$) 알고리즘

인트로

알고리즘을 배우다가 Big-O 표기법으로 크기비교도 해보았지만 O(logn)같은 복잡도를 가지는 알고리즘은 어떻게 구현되었을지 궁금했다.

1. O($\log n$) 알고리즘

algorithm doSomething(n):
    count, k = 0, 1
    while k < n do
        k *= 2
        count += 1
    return count

설명:

k는 1부터 2배씩 커지면서 n에 가까워진다.
따라서 반복문 내부의 연산을 c번이라고 하면
전체 알고리즘의 연산횟수는 $c \times \log_2 n$ 번 수행

수행시간: O($\log n$)

※ Big-O에서 log를 사용할때 밑을 생략하는 경우가 많다.

자세히:

$k:2^0,2^1,2^2,\cdots,2^{k-1},2^k,\cdots$
k가 위와 같은 값을 가질 때, 만약 n이 $2^{k-1} < n \leq 2^k\cdots(i)$ 이라면(반복문 내에서 c번의 연산수행한다면) 위 반복문을 k번 돌고 빠져나았을 것이다. -> O($c\times k$)
k말고 n의 관한식으로 나타내기 위해 $(i)$식 양변에 $log_2$를 취하면 $k-1 < log_2 n \leq k$ --> $k < log_2 n +1$ 이 성립
따라서 O($c\times k$) = O($c\times log_2 n + c$) = O($\log n$)

※ Big-O는 상한(Upper Bound)의 개념이다. 즉, 어떠한 최악의 경우에도 해당 알고리즘은 Big-O만큼의 시간복잡도를 보장한다고 할 수 있다.
아래에 잘 정리된 블로그가 있다.
시간복잡도 개념설명 및 비교

2. O(sqrtn) = O($\sqrt{n}$) 알고리즘

algorithm doSomething(n):
    count, k = 0, 1
    while k*K <= n do
        count += 1
        k += 1
    return count

설명:

k*k는 $1^2,2^2,3^2,\cdots$ 처럼 커지면서 n에 가까워진다.
따라서 반복문 내부의 연산을 c번이라고 하면
전체 알고리즘의 연산횟수는 $c\times\sqrt{n}$ 번 수행한다.

수행시간: O($\sqrt n$)

자세히:

$k: 1, 2, 3, \cdots,\sqrt n, \sqrt {n+1}, \cdots$
k가 위와 같이 커질 때
k*k <= n 인 동안 반복문이 수행되다가 k*k > n 이 되는 순간 반복문에서 나오므로 k <= $\sqrt n$ 인 동안 반복문 내부연산 c번 수행하므로
알고리즘 총 연산횟수는 c$\times$n번 이므로 -> O($\sqrt n$)

3. O(n) 알고리즘

algorithm doSomething(n):
    for i=0 to n/2 do
        temp = A[i]
        A[i] = A[n-1-i]
        A[n-1-i] = temp
    return A

설명:

i는 0부터 n/2까지 1씩 증가하기 때문에 반복문 내부 연산횟수를 c를 $\frac{n}{2}-0+1$(마지막항 - 초항 + 1을 하면 반복횟수 구할 수 있다.) -> O($c\times \frac{n}{2}+c$)이다.

수행시간: O(n)

4. O($n^2\log n$) 알고리즘

algorithm doSomething(n):
    count = 0
    for i=0 to n do
        for j=0 to n do
            k = 1
            while k <= n do
                k *= 2
                count += 1
    return count

설명:

이중 for문이므로 반복문이 $n^2$번 수행되고 내부연산 중 또 반복문이 있다. 이 while문은 앞서 "1. O($\log n$) 알고리즘"에서 살펴본대로 k가 2배씩 커지기 때문에 $\log n$번 수행되므로 -> O($c\times logn$)

수행시간: O($n^2\log n$)