시간복잡도 & 공간 복잡도

시간 복잡도와 공간 복잡도

• 시간 복잡도 : 알고리즘을 위해 필요한 연산의 횟수
  => 얼마나 오래 걸리는 지
  
• 공간 복잡도 : 알고리즘을 위해 필요한 메모리의 양
  =>얼마나 많은 메모리를 차지하는 지
  
  

시간 복잡도

• 시간 제한 : 일반적으로 푸는 시간이 아니라 작성한 프로그램이 모든 입력을 받아 이를 처리하고 실행 결과를 출력하는 데까지 걸리는 시간을 의미
  

• 빅오 표기법 : 가장 빠르게 증가하는 항만을 고려하는 표기법
  
  

array = [3, 4, 1, 2,6]

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

만약 이러한 코드가 있으면 2중 반복문으로 N x N으로 O(N^2)임!
하지만 모든 2중 반복문이 O(N^2)형태는 아니니 유의.

=>O(N^3)을 넘어가면 실제 코딩테스트에 쓰기에는 적합하지 않음.
그래서 문제의 조건을 보고, 이에 적합한 시간복잡도로 동작하는 알고리즘을 작성해야함.

공간 복잡도

• 공간 복잡도 빅오 표기법 이용 - 대부분 리스트를 이용해 풀음!

  ---

시간과 메모리 측정

#수행 시간을 측정할 수 있는 코드

import time
start_time = time.time()

#프로그램 소스 코드
end_time = time.time()
print("time : ", end_time - start_time)