*나동빈님의 이코테 2021 강의 정리 (https://www.youtube.com/watch?v=m-9pAwq1o3w&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC)

복잡도(Comoplexity)

• 복잡도는 알고리즘의 성능을 나타내는 척도.
  • 시간복잡도: 알고리즘의 수행시간 분석. 시간복잡도가 높으면 실행 시간 많이 소요, 낮으면 적게 소요.
  • 공간복잡도 : 알고리즘의 메모리 사용량 분석. 공간복잡도가 높으면 많은 메모리사용.
• 복잡도가 낮을수록 좋은 알고리즘.

빅오 표기법(Big-O Notatino)

• 가장 빠르게 증가하는 항만을 고려하는 표기법-> 함수의 상한만을 나타냄

시간복잡도 O(N)

array=[1,2,3,4,5] # N=5
result= 0
for i in array:
	result += i
print(result)

수행 시간은 데이터의 개수 N에 비례하기 때문에 시간복잡도는 O(N).

시간복잡도 O(N^2)

array = [1,2,3,4,5]
for i in array:
	for j in array:
    	temp = i*j;
        print(temp)  

2중 반복으로 돌기 때문에 5*5가 되어서 시간복잡도는 O(N^2).
모든 2중반목문의 시간복잡도가 O(N²)는 아님. 소스코드가 내부적으로 다른 함수를 호출한다면, 그 함수의 시간복잡도까지 고려해야함.

요구사항에 따른 알고리즘 설계

• 문제에서 가장 먼저 확인해야하는 내용은 시간제한(수행시간 요구사항).
• 시간제한이 1초인 문제일 경우, 일반적인 기준
  - N의 범위가 500인 경우: 시간복잡도가 O(N^3)인 알고리즘.
  - N의 범위가 2,000인 경우: 시간복잡도가 O(N^2)인 알고리즘.
  - N의 범위가 100,000인 경우: 시간복잡도가 O(NlogN)인 알고리즘.
  - N의 범위가 10,000,000인 경우: 시간복잡도가 O(N)인 알고리즘.

알고리즘 문제해결과정

1. 지문 읽기 및 컴퓨터적 사고
2. 요구사항(복잡도) 분석
3. 문제해결을 위한 아이디어 찾기
4. 소스코드 설계 및 코딩

수행시간 측정 소스코드

import time
start_time = time.time() # 측정시작
end_time = time.time() # 측정 종료
print("time:",end_time - start_time) # 수행시간 출력