[알고리즘] 시간복잡도 Big-O

코딩테스트를 공부하다보면 시간복잡도를 계산하면서 푸는 멋쟁이 분들을 볼 수 있다.
난 아직 멋쟁이가 아니다... 시간 복잡도 마스터하기 위해 오늘은 이 포스트를 쓴다!

우선 알고리즘이 빠르다 는건 시간 초 기준으로 결정되는 것이 아님!
왜냐하면 컴퓨터 하드웨어 성능에 따라 같은 알고리즘이여도 시간 초가 다르기 때문이지~
따라서 알고리즘 속도는 "완료까지 걸리는 절차의 step 수" 로 결정된다.

상수 시간 (Constant Time)

N이 얼마나 크든지 상관없이 동일한 숫자의 스텝이 필요함 ➡️ O(1)

# 무조건 배열의 첫번째 원소만 출력!

def print_first(arr):
	print(arr[0])

선형 검색 (Linear Search Algorithm)

요소 하나씩 검사하는 알고리즘
input size에 따른 시간 복잡도를 가진다. ➡️ O(N)

for a in arr:
	print(a)

• n번 작업이 단순히 2번, 3번... 반복되어도 O(2N)이 아닌 O(N)이라 표기함

for a in arr:
	print(a)
for a in arr:
	print(a)

2차 시간 (Quadratic Time)

n번의 루프 안에서 n번의 루프를 실행한다. ➡️ O(N^2)

• 중첩 반복문

# n이 10이라면, 10*10의 100번의 step이 필요
for a in arr:
	for b in arr:
    	print(a, b)

로그 시간 (Logarithmic Time)

• 이진 검색 알고리즘 ➡️ O(log N)

n = log 32   →   (밑은 2라고 가정)
2^5 = 32 이므로 n은 5 = (5 step)
선형 검색이라면 32 step이지만, 이진 검색(로그 시간)이라면 5 step

이진 검색

• 정렬된 배열(sorted array)에서만 사용 가능하다.
• index 0부터 시작하는 것이 아닌, 배열의 가운데 index에서 시작 (mid)
  • mid index로 나눈 2개의 배열 중 target과 관련있는 배열로 범위를 좁힌 후, 또 그 배열의 가운데 index부터 탐색
    ➡️ 이진 검색은 매 step마다 절반의 item을 제외함 (굉장히 효율적!)