알고리즘 성능 평가

1. 복잡도(Complexity)

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

• 시간 복잡도 : 특정한 크기의 입력에 대하여 알고리즈므이 수행 시간 분석
• 공간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석

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

Q. 코드가 복잡하다 ≠ 복잡도
⇒ 복잡도는 함수의 성능에 관련된 것

3) 시간 복잡도가 높다는 것은 알고리즘의 실행 속도가 느리다 (수행시간 오래걸림)

4) 공간 복잡도가 높다는 것은 많은 메모리가 필요하다는 것

⇒ 기능적으로는 복잡도가 낮을 수록 좋은 알고리즘

2. 복잡도 표기법

1) 빅오 표기법

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

ex) 3N^3 + 5N^2+1000000

→ O(N^3) 으로 표현 가능 ( 최고 차수의 계수는 무시 )

빅오 표기법의 개념 극한으로 생각 ⇒ n이 커질 수록 $N^3$이 엄청나게 커져서 다른 항들은 무시됨

따라서 최고 차수의 항 만을 표시!

3. 시간 복잡도 계산해보기

1. N개의 데이터의 합을 계산하는 프로그램 예제

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

#모든 데이터를 하나씩 확인하며 합계를 계산

for x in array:
    summary += x

#결과를 출력
print(summary)

수행 시간은 데이터의 개수 N에 비례할 것임을 예측할 수 있음

모든 데이터를 한번씩 확인하면서 더하기 때문!

→ 수행시간은 데이터 개수가 늘어나는 것에 선형적으로 비례하면서 늘어남

⇒ 시간 복잡도 : O(N)

2. 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)

+) 모든 2중 반복문의 시간 복잡도가 O(N^2)인 것은 아니다

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

4. 알고리즘 설계 TIP

일반적으로 CPU 기반의 개인 컴퓨터나 채점용 컴퓨터에서 연산 횟수가 5억을 넘어가는 경우

• C언어 기분, 통상 1 ~ 3초 가량의 시간 소요

• Python 기준으로 통상 5 ~ 15초 가량의 시간이 소요

  • PyPy의 경우 가끔 C언어보다 빠르게 동작⇒ python으로 제출 후 안되면 pypy로 제출도 해보기

  • ⇒ pypy지원한다면 pypy로 제출하는게 시간복잡도 측면에서는 좋지만, 많은 메모리가 사용될 수 있음

Q. O(N^3)의 알고리즘을 설계한 경우, N의 값이 5,000이 넘는다면 얼마나 걸릴까요?

답 : 5000^3

python이 1초에 약 5000만번의 연산을 한다고 가정 ⇒ 2500초 걸림

python이 1초에 약 2000만번의 연산을 한다고 가정하고 문제 풀기

⇒ 채점용 서버 컴퓨터 성능에 따라 천차 만별일 수 있음

• 코딩 테스트 문제에서 시간제한은 통상 1 ~ 5초 가량인 것에 유의

  • 혹여 문제에 명시되어 있지 않은 경우 대략 5초 정도라고 생각하고 문제를 푸는 것이 합리적

5. 요구 사항에 따라 적절한 알고리즘 설계하기

1) 문제에서 가장 먼저 확인해야 하는 내용 ⇒ 시간제한(수행시간 요구사항)

2) 시간 제한이 1초인 문제를 만났을 때, 일반적인 기준은 다음과 같음

• N의 범위가 500인 경우 : 시간 복잡도가 O(N^3)인 알고리즘을 설계하면 문제 해결 가능

• N의 범위가 2,000인 경우 : 시간 복잡도가 O(N^3)인 알고리즘을 설계하면 문제 해결 가능

• N의 범위가 100,000인 경우 : 시간 복잡도가 O(NlogN)인 알고리즘을 설계하면 문제 해결 가능

• N의 범위가 10,000,000인 경우 : 시간 복잡도가 O(N)인 알고리즘을 설계하면 문제 해결 가능

⇒ 여러가지 이유로 시간 초과가 될 수 있음!

시간 제한에 따라 적절한 알고리즘을 설계하는 것은 많은 문제를 풀어보면서 감을 잡기

6. 알고리즘 문제 해결 과정

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

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

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

4) 소스 코드 설계 및 코딩

⇒ 일반적으로 대부분의 문제 출제자들은 핵심 아이디어를 캐치하면, 간결하게 소스 코드를 작성할 수 있도록 문제 출제

문제에 접근할 때, 생각나는 내용을 바로 소스 코드로 옮기기 보다는, 문제를 온전히 이해하고 코드를 어떻게 작성해 나갈지 고민하고 코드 작성하기

7. 수행시간 측정 소스코드 예제

import time
start_time = time.time()

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

위의 python 코드로 수행 시간을 측정해보면서 코드를 짜본다