1. 시간 복잡도 표기법 알아보기

알고리즘에서 시간 복잡도는 주어진 문제를 해결하기 위한 연산 횟수를 말합니다. 일반적으로 파이썬 프로그램에서는 2,000만번~1억번의 연산을 1초의 수행 시간으로 예측할 수 있습니다.

 

시간복잡도 정의하기

실제 시간 복잡도를 정의하는 3가지 유형은 다음과 같습니다.

 

시간복잡도 유형

-빅오메가 : 최선일때(best case)의 연산 횟수를 나타낸 표기법

-빅세타:보통일때(average case)의 연산횟수를 나타낸 표기법

-빅-오: 최악일때(worst case)의 연산 횟수를 나타낸 표기법

 

다음은 1~100사이의 무작윗값을 찾아 출력하는 코드입니다. 빅-오메가 표기법의시간 복잡도는 1번, 빅-세타 표기법의 시간 복잡도는 N/2번, 빅-오 표기법의 시간복잡도는 N번입니다.

 

#시간복잡도의 예시입니다.

import random
findNumber = random.randrange(1, 101)

for i in range(1, 101):
	if i == findNumber:
    print(i)
    break

 

01-2 시간 복잡도 활용하기

 

# 1. 수 정렬하기

N개의 수가 주어졌을때 이를 오름차순 정렬하는 프로그램을 작성하라.

 

#<입력 조건>
#1번째 줄에 수의 개수 N(1 < N < 100), 2번째 줄부터는 N개의 줄에 숫자가 주어진다. 
이 수는 절댓값이 100보다 작거나 같은 정수이다. 수는 중복하지 않는다.

#<출력 조건>
#1번째 줄부터 N개의 줄에 오름차순 정렬한 결과를 1줄에 1개씩 출력한다.
#예제입력
5
5
2
3
4
1
#예제 출력
1
2
3
4
5
###

-->
num = 100
cnt = 1

1)
for i in range(num):
	print("연산횟수 : ", +str(cnt))
    cnt +=1
-->
1
1
2
2
...
100




#2)
num = 100
cnt = 1

for i in range(num):
    for j in range(num):
        print("연산횟수 : " + str(cnt))
    cnt += 1
-->   
1
1
1
1
2
2
...
10

 

-문제를 풀때 연산 횟수는 2,000만번 연산하는것을 기준으로 생각합니다.

-또한 시간 복잡도는 항상 최악일때 즉 데이터의 크기가 가장 클때를 기준으로 합니다.

 

연산 횟수 계산방법

-연산 횟수 = 알고리즘 시간 복잡도 n값에 데이터릐 최대 크기를 대입하여 도출

-->위 공식을 대입해 각 알고리즘이 이 문제에 적합한지 판단해본다

이와 같이 시간 복잡도 분석으로 문제에서 사용 할 수 있는 알고리즘을 선택할 수 있고, 이 범위를 바탕으로 문제의 실마리를 찾을 수 있다. 즉, 데이터의 크기(N)를 단서로 사용해야 하는 알고리즘을 추측해 볼 수 있다.

 

시간복잡도는 작성한 코드의 비효율적인 로직을 개선하는 바탕으로도 사용할 수 있습니다. 이 부분을 활용하려면 가장 먼저 코드의 시간 복잡도를 도출할 수 있어야 합니다. 시간 복잡도를 도출하려면 다음 2가지 기준을 고려해야합니다.

 

시간 복잡도 도출 기준

-1. 상수는 시간 복잡도 계산에서 제외한다.

-2.가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다.