1. What is Big-O notation ?

• 우리는 알고리즘 실행 효율성을 측정할 척도가 필요하고, Big-O 표기는 이를 수학적으로 표현해주는 표기법이다.

• Big-O 표기법은 해당 코드가 얼마나 수행되었는지(결과값을 출력하기 위한 연산을 얼마나 반복했는지)에 따라 효율성을 확인한다.

• Big-O 표기법은 데이터 입력값 크기에 따라 알고리즘 실행 속도의 변화를 설명하는 방법이다.
  ! 빅오표기법은 실제 러닝타임을 표기하는 것보다 데이터, 사용자 증가에 따른 알고리즘 성능을 예측하는 것이 목표다.

• 알고리즘 계산 복잡도 종류

  • 시간 복잡도(time complexity) : 알고리즘을 활용해 얼마만큼의 실행시간이 걸렸는가
  • 공간 복잡도(space complexity) : 문제해결을 위해 얼마만큼의 메모리 저장 공간이 필요한가
    ! 하드웨어의 성능이 좋아짐에 따라 공간 복잡도보다는 소프트웨어의 성능인 시간 복잡도가 더 중요해졌다.

Big-O run times 비교

아래 그래프처럼 입력값(x축의 n값)에 따른 실행시간(y축의 N값)이 증가폭에 의해 효율을 판단할 수 있다.

2. Big-O run times

2.1. constant time(상수시간) : $O(1)$

(이미지출처)
입력데이터의 크기에 상관없이 언제나 일정한 시간이 걸리는 알고리즘 (알고리즘이 문제를 해결하는데 오직 한 단계만 거친다.)

def print_one_item(items):
    print(items[1]) #상수시간(단순하게 하나의 출력)

print_one_item([0,1,2])
# 1

2.2. logarithmic time (로그시간) : $O(log n)$

(이미지출처)
대표적인 알고리즘으로 '이진탐색'이 있으며, 이진탐색은 정렬을 기본전제로 가능한 탐색방법이다.
입력데이터 n이 주어졌을 때, 문제를 해결하기 위해 필요한 단계들이 연산마다 특정 요인에 의해 줄어든다.

2.3. linear time(선형시간) : $O(n)$

(이미지출처)
입력 데이터 크기에 비례해서 처리시간이 걸리는 알고리즘 (문제 해결 단계와 입력값 n이 1:1 관계를 가진다.)

def print_every_item(items):
    for item in items: #하나의 반복문
        print(item)

print_every_item([0,1,2])
# 0
# 1
# 2

2.4. Quadratic time(제곱시간) : $O(n^2$)

(이미지출처)
반복문이 중첩된 형태인 중첩반복문이 제곱시간 복잡도를 가진다.

def print_pairs(items):
    for item_one in items: #중첩반복문
        for item_two in items:
            print(item_one, item_two)

print_pairs([0,1,2])
# 0 0
# 0 1
# 0 2
# 1 0
# 1 1
# 1 2
# 2 0
# 2 1
# 2 2

3. Big-O with codes

3.1.

만약 소스코드가 다음과 같다면?

def time_test(items):
    last_idx = len(items) - 1
    print(items[last_idx])      # 상수시간
    
    print("===반복문1 시작===")
    middle_idx = len(items) / 2
    idx = 0
    while idx < middle_idx:     # 반복문1: 선형시간
        print(items[idx])
        idx = idx + 1
    
    print("===반복문2 시작===")
    for num in range(100):     # 반복문2: 선형시간 
        print(num)

time_test([0,1,2])

#
2
===반복문1 시작===
0
1
===반복문2 시작===
0
1
2
3
4

선형 시간이 상수 시간보다 우선시 되므로 상수시간은 무시되고, 독립적으로 수행되는 반복문으로 인해 아래 코드에 대한 런타임은 선형시간(linear time), 즉 $O(n)$이 된다.

3.2.

def test(n):
    i = 1
    while i < n:
        print(i)
        i *= 2

test(10)

#
1
2
4
8

입력값과 출력값의 크기가 동일하지 않기 때문에 선형시간($O(n)$)이 될 수 없다.
입력값인 n에 따라 출력값인 i의 증가율이 동일하지 않으므로 로그 시간(logarithm time)으로 측정된다. ($O(logn)$)

3.3.

array_test = [3,1,7]

def example_sort(array_test):
  array_len = len(array_test)
  print('array_len:', array_len)

  array_test.append(5) # [3, 1, 7, 5]
  array_test.extend([2,9]) # [3, 1, 7, 5, 2, 9]
  array_test.pop() # [3, 1, 7, 5, 2]
  print('array_test:', array_test)
  print('array_len:', len(array_test))

  for i in range(1, array_len): # i: 1, 2, 3, 4
    # 한 번 수행되고 더 이상 반복되지 않는 반복문이다.
    for j in range(i, 0, -1):
      if array_test[j] < array_test[j-1]:
        print(i, j)
      else:
          break


example_sort(array_test)
# array_len: 3
# array_test: [3, 1, 7, 5, 2]
# array_len: 5
# 1 1

위의 코드에는 중첩반복문이 있기에 빅오표기법에 의해 제곱시간($O(n^2)$)으로 착각할 수 있으나, 두번째(중첩)반복문의 반복횟수가 1에 그치기 때문에 사실상 총 반복문의 수는 1개라고 볼 수 있다.
따라서, 위의 코드의 시간복잡도는 빅오표기법에 의해 $O(n)$ 선형시간이 된다.

created on Nov 22, 2021

• 글 작성