알고리즘 수행 시간

알고리즘은 최대한 효율적으로 짜여져야 한다. 떄문에 우리는 알고리즘의 수행시간을 고려해서 짜야한다. 알고리즘의 수행시간을 어떻게 알 수 있을까? 간단한 예제들을 살펴보면서 파악해보자.

if 시간 복잡도 == C (C는 상수)

알고리즘 복잡도가 상수일 떄의 코드를 간단하게 살펴보자. 이 경우는 for문이 없는 경우일 것이다.

def add(a, b):
	return a+b

다음 경우는 복잡도가 O(1)일 것이다.

if 시간 복잡도 == C * n (C는 상수)

우리는 시간 복잡도를 계산할 떄 n을 많이 넣어준다. n은 중요한 변수이다. n에 따라서 시간 복잡도가 결정된다. 시간복잡도가 n에 비례하는 코드를 한 번 보자. for문이 한번만 나오는 코드이다.

def sample(n):
	sum = 0
    for i in range(n):
    	sum += i
     return sum

다음 경우는 복잡도가 O(n)일 것이다.

if 시간 복잡도 == C * n ^ 2

다음 경우는 이중 for 문을 썼을 경우이다.

def sample2(n):
	for i in range(1, n+1):
    	for j in range(1, n+1):
        	print(f"{i} * {j} == {i*j}")

이런식으로 코드를 짜게 되면 시간 복잡도가 O(n^2)이 나온다.