data structure(자료 구조) - Big - O notation::FBTT

https://readytoearndon.tistory.com/16

data structure(자료 구조) - 점근적 분석, 점근 표기법

점근 표기법 중 하나인 Big - O 표기법의 예에 대해서 다루니 위의 글을 먼저 보고 오실 것을 추천드립니다.

 

n	1	log n	n	n log n	n ^ 2	2 ^ n
1	1	0	1	0	1	2
10	1	1	10	10	100	2^10
100	1	2	100	200	10,000	2^100
1,000	1	3	1,000	3,000	1,000,000	2^1,000

위의 표는 각 함수들의 시간 복잡도를 비교한 것입니다. 대표적인 몇 가지 함수만을 나타냈습니다. 왼쪽으로 갈수록 투입되는 자원이 적은, 성능이 좋은 함수입니다. 

 

예) g(n) = n (선형 시간 복잡도(linear time complex))

f(n) = O(n)

 

sum = 0
n = int(input())
for i in range(n):
    num = int(input())
    sum += num
print(sum)

예) g(n) = n^2 (다항 시간 복잡도(polynomial time complex))

f(n) = O(n ^ 2)

 

n = int(input())
for i in range(n):
    for j in range(n):
        print('hello')

예) g(n) = 2 ^ n

f(n) = O(2^n)

 

def fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)