시간 복잡도

코딩테스트에서 시간복잡도를 나타낼 때 빅오(Big-O)표기법을 사용한다.

• 시간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지 의미
• 빅오 표기법 : 가장 빠르게 증가하는 항만을 고려하는 표기법

EX) N개의 데이터가 있을 때, 모든 데이터의 값을 더한 결과를 출력하는 프로그램

array = [3, 5, 1, 2, 4] # 5개의 데이터 (N = 5)
sum = 0  # N이 커짐에 따라 무시할 수 있을 정도로 작아짐(무시)

for x in array: # 가장 영향력이 큰 부분 : N에 비례
	summary += x
    
print(summary) # N이 커짐에 따라 무시할 수 있을 정도로 작아짐(무시)

시간 복잡도 : O(N)
(연산 횟수 5회) - 실제 연산 횟수는 다를 수 있음.

EX) 단순 상수 연산하는 프로그램

a = 5
b = 7
print(a + b)

시간 복잡도 : O(1) : 단순 상수 연산이므로 시간 복잡도 O(1)로 표현가능하다.
(연산 횟수 1회) - 실제 연산 횟수는 다를 수 있음.

EX) 각 원소에 대하여 다른 모든 원소에 대한 곱셈 결과를 매번 출력하는 프로그램

array = [3, 5, 1, 2, 4] # 5개의 데이터(N = 5)

for i in array:
	for j in array : 
    	temp = i * j
        print(temp)
        

시간 복잡도 : O(N^2) : 간단한 2중 반복문 N X N의 연산이 필요하다.
모든 2중 반복문의 시간 복잡도가 O(N^2)은 아니다. 내부적으로 다른 함수를 호출한다면 내부 함수의 시간 복작도까지 고려해야한다.

• 시간 복잡도 표 (위쪽에 있을수록 빠르다.)

  빅오 표기법	명칭
  O(1)	상수 시간
  O(logN)	로그 시간
  O(N)	선형 시간
  O(NlogN)	로그 선형 시간
  O(N^2)	이차 시간
  O(N^3)	삼차 시간
  O(2^n)	지수 시간

• 연산 횟수 10억(0이 9개) ~= 1초

• 시간 복잡도가 동일해도 실제 연산 횟수에는 차이가 있을 수 있다.

• 시간이 1초인 문제에 대하여 다음과 같이 유추할 수도 있다.

  • N이 500인 경우 : 시간복잡도 O(N^3)인 알고리즘을 설계하면 문제를 풀 수 있다.
  • N이 2000인 경우 : 시간 복잡도가 O(N^2)인 알고리즘을 설계하면 문제를 풀 수 있다.
  • N이 100,000인 경우 : 시간 복잡도가 O(NlogN)인 알고리즘을 설계하면 문제를 풀 수 있다.
  • N이 10,000,000인 경우 : 시간 복잡도가 O(N)인 알고리즘을 설계하면 문제를 풀 수 있다.

• 시간 측정

  import time
  start_time = time.time()
  #측정하고 싶은 알고리즘(소스코드)
  ####
  ###
  ###
  end_time = time.time()
  print("time :", end_time - start_time) # 수행 시간 출력