[코테] 시간 복잡도

컴퓨터가 초당 연산할 수 있는 최대 횟수는 1억(100,000,000)번

시간복잡도는 연산의 수를 세어서 연산을 몇 번 하느냐를 통해 대략적으로 계산할 수 있다

여러가지 방법이 있지만 가장 일반적으로 Big-O 방법을 사용한다

Python에서 기본 산술 연산들은 O(1)의 시간복잡도를 가짐

예시를 통해 감을 잡아보자면

1) 길이가 n인 list를 처음부터 끝까지 한번씩 출력
: O(1)*n=O(n)

2) 별찍기 문제 - 주어진 숫자 n에 대해 별을 1부터 n개까지 늘려가며 출력한다
: 출력 한 번이 하나의 연산이기 때문에
1 + 2 + ... + n = n(n+1)/2
즉, O(n^2)

3) 박테리아 수명 문제 - 해마다 반씩 세포가 죽을 때 언제 죽을지 계산
: 초기 박테리아 수 = n
K년 후 박테리아 수 = n/(2^K)
소멸할 때의 K값 > log_2(n)
결국 log_2(n)을 계산해야 하는데 이때 n을 표현하기 위한 비트 크기에 대한 시간 복잡도가 고려됨. log 연산 자체는 O(1). 때문에 입력을 표현하기 위한(2bit) 복잡도가 log(n)