01. Big-O 표기법

Big-O 표기법

수행시간 함수 가 여러항의 항의 합으로 표현된다면, 함수 값의 증가율이 가장 큰 항으로 표기하는게 시간분석을 간단하게 도움이 된다.
- 예를 들면, T(n) = 2n + 5이면, 상수항보단, n의 일차항의 T(n)의 값을 결정 -> 즉 상수항 생략해도 문제 X
- T(n) = n^2 + 4n + 4 이면, n값이 커지면서 n^2의 값이 T(n)의 값을 결정함으로 일차항, 상수항 생략해도 문제 X
즉, 이렇게 최고차항만 남기고 나머지를 생략해서 수행시간 간략히 표기하는 방법을 근사적 표기법(Asymptotic Notation)이라 하고, Big-O(대문자 O)를 이용하여 표기한다.

T(n) = 2n + 5 --> T(n) = O(n)
T(n) = n^2 + 4n + 4 --> T(n) = O(n^2)

O 시간 알고리즘 종류

O(1) 시간 알고리즘: constant time algorithm: 값을 1 증가시킨 후 리턴
```
def increment_one(a):
  return a+1
```
O(log n) 시간 알고리즘: log의 밑은 2라고 가정하고 n을 이진수로 표현했을 때의 비트수 계산 알고리즘
```
def number_of_bits(n):
  count = 0
  while n > 0:
    n = n // 2
    count += 1
  return count
```
O(n) 시간 알고리즘 : linear time algorithm: n개의 수 중에서 최대값 찾는 알고리즘

시간 알고리즘: quadratic time algorithm: 두 배열 A, B의 모든 정수 쌍의 곱의 합을 계산하는 알고리즘

# pseudo code
algorithm array_sum(A, B, n):
  sum = 0
  for i = 0 to n - 1 do
  for j = 0 to n - 1 do
    sum += A[i]*B[j]
  return sum
end_algorithm

시간 알고리즘: cubic time algorithm: n x n인 2차원 행렬 A와 B의 곱을 계산하여 결과 행렬 C를 리턴하는 알고리즘

# pseudo code
algorithm mult_matrices(A, B, n)
  input: n x n 2d matrices A, B
  output: C = A x B
    
  for i = 1 to n do
  for j = 1 to n do
    C[i][j] = 0
  for i = 1 to n do
  for j = 1 to n do
    for k = 1 to n do
    C[i][j] += A[i][k] * B[k][j]
  return C
end_of_algorithm

이상의 시간이 필요한 알고리즘: exponential time algorithm: k번째 피보나치 수 계산하는 알고리즘

def fibonacci(k):
  if k <= 1: return k
  return fibonacci(k-1) + fibonacci(k-2)

Big-O 연습

Big-O(n)

algorithm doSomething(A, n):
  for i = 0 to i < n/2 do
    c = A[i]
    A[i] = A[n-1-i]
    A[n-1-i] = c
end_of_algorithm

= O(n)

Big-O(n^2log n)

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

= O(n^2 long n)

Big-O(sqrt n)

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

= O(n^{0.5}) = O(sprt(n))

Big-O(log n)

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

= O(log n)

Data Structure (2) - 간단표기법 (Big-O)

간단표기법 Big-O