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

* 본 포스팅은 나동빈 - 이코테 2021 강의 몰아보기 에서 학습한 내용을 포스팅합니다.

---

출처

동빈나 이코테

 

■ 복잡도(Complexity)

복잡도는 알고리즘의 성능을 나타내는 척도

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

    ● 공간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석

동일한 기능을 수행하는 알고리즘이 있다면, 일반적으로 복잡도가 낮을수록 좋은 알고리즘이다.

 

 

■ 빅오 표기법(Complexity)

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

    ● 함수의 상한만을 나타내게 된다.

 

3N³ + 5N² + 1,000,000

    ● 빅오 표기법에서는 차수가 가장 큰 항만 남기므로 O(N³)으로 표현

 

 

 

■ 시간 복잡도 계산해 보기 ①

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)

▶ 시간 복잡도 : O(N²)

모든 2중 반복문의 시간 복잡도가 O(N²)인 것은 아님

소스코드가 내부적으로 다른 함수를 호출한다면 그 함수의 시간 복잡도까지 고려

 

 

■ 알고리즘 설계 Tip

연산 횟수가 5억을 넘는 경우

    ● C언어 : 1 ~ 3초가량 소요

    ● Python : 5 ~ 15초가량 소요

        ● PyPy : 때때로 C언어보다 빠르게 동작 but 메모리 소요가 클 수 있음

 

O(N³)의 알고리즘을 설계(N = 5000)

    ● 연산 횟수 : 1250억   

    ● python이 1초에 5000만 번 계산한다면 약 2500초 정도 소요

 

 

■ 알고리즘 문제 해결 과정

1. 지문 읽기 및 컴퓨터적 사고

2. 요구사항(복잡도) 분석

3. 문제 해결을 위한 아이디어 찾기

4. 소스코드 설계 및 코딩

 

 

■ 수행 시간 측정 소스코드

import time
start_time = time.time() # 측정 시작

# 프로그램 소스코드
end_time = time.time() # 측정 종료
print("time:", end_time - start_time) # 수행 시간 출력