[알고리즘] 알고리즘 성능

🫧 복잡도

시간복잡도

특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석

공간복잡도

특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석

🫧 빅오 표기법

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

코딩 테스트 문제에서 시간 제한은 통산 1~5초 가량이다.
대략 5초 정도라고 생각하고 문제를 푸는 것이 합리적이다.

해당 코드의 수행시간은 데이터 개수 N에 비례
➡️ 시간복잡도: $O(N)$

array = [3, 5, 1, 2, 4] # 5개의 데이터(N=5)
summary = 0 # 합계를 저장할 변수

# 모든 데이터를 하나씩 확인하며 합계를 계산
for x in array:
	summary +=x
    
# 결과를 출력
print(summary)

해당 코드의 수행시간은 데이터 N의 제곱에 비례
➡️ 시간복잡도: $O(N^2)$

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

# 모든 데이터를 하나씩 확인하며 합계를 계산
for i in array:
	for j in array:
		temp = i*j
        print(temp)

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

문제에서 가장 먼저 확인해야 하는 내용은 시간 제한이다.
시간 제한이 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_tim = time.time()
print("time:", end_time - start_time)

---

Reference

이코테