복잡도

알고리즘의 성능을 객관적으로 평가하는 기준

공간 복잡도

메모리와 파일 공간이 얼마나 필요한지 평가

시간 복잡도

실행하는 데 필요한 시간을 평가

def seq_search(a: Sequence, key: Any) -> int:
	i = 0					# 1 : 1번 실행
    while i < n:			# 2 : n/2 번 실행
    	if a[i] == key:		# 3 : n/2 번 실행
        	return i		# 4 : 1번 실행
		i += 1				# 5 : n/2 번 실행
	return -1				# 6 : 1번 실행

n 에 비례하는 횟수만큼 실행되면 O(n) 의 복잡도를 가진다

O(max(1, n/2, n/2, 1, n/2, 1)) = O(n)

가장 높은 복잡도를 선택, 위의 선형검색의 복잡도는 O(n) 이다.

# 시간복잡도 체감
import sys
n = int(sys.stdin.readline())

a = [1, 1]                                              # n / 10000을 넣어도 바로
if n == 1: print(1)
elif n == 2: print(1)
else:
    for x in range(2, n):
        a.append(a[x-1]+a[x-2])
    print(a[n-1])

# def fibonacci(n):                                     # 2^n / 30 넘어가면 ...
#     if n <= 1:
#         return 1
#     return fibonacci(n - 1) + fibonacci(n - 2)

# print(fibonacci(n-1))