복잡도

시간 복잡도

• 알고리즘을 위해 필요한 연산의 횟수를 의미한다.

• 빅오(Big-o) 표기법을 사용한다.

  • 빅오(Big-o) 표기법
    알고리즘의 효율성을 분석하기 위해 사용되는 수학적 표기법으로, 특정 입력 크기에 대해 알고리즘이 얼마나 빠르게 실행되는지(시간 복잡도) 또는 얼마나 많은 메모리를 사용하는지(공간 복잡도)를 표현한다.
    빅오 표기법은 최악의 경우를 고려한 상한선을 나타내며, 입력 크기 n에 대해 알고리즘의 성능이 어떻게 변하는지 설명한다.

• 최악의 경우의 시간 복잡도를 우선적으로 고려해야 한다.

• 시간 복잡도 명칭

  • O(1): 상수 시간(Constant time)

  • O(logN): 로그 시간(Log time)

  • O(N): 선형 시간

  • O(NlogN): 로그 선형 시간

  • O(N^2): 이차 시간

  • O(N^3): 삼차 시간

  • O(2^n): 지수 시간

  
  

• 경우에 따라 차수가 작은 항들도 고려를 해야하기 때문에 빅오 표기법이 항상 절대적인 것은 아니다.

  • 예를 들어, 연산 횟수가 3N^2 + 5N^2 + 1,000,000인 경우에 N이 작을 경우 상수 값이 미치는 영향이 크기 때문이다.

• 일반적으로 코딩 테스트 환경에서는 O(N^3)을 넘어가면 문제 풀이에서 사용하기 어렵다.

• N의 크기에 따른 시간 복잡도의 연산 횟수의 분포 (낮은 항에 따라 실제 연산 횟수는 다를 수 있음)

  • O(N): 1,000

  • O(NlogN): 10,000

  • O(N^2): 1,000,000

  • O(N^3): 1,000,000,000

  
  

• 문제의 조건부터 확인하여 문제를 풀기 위해 얼마나 효율적인 알고리즘을 작성해야 하는지 판단할 수 있다.

  • 예를 들어, 데이터의 개수 N이 1,000만 개를 넘어가면 시간 제한이 1초라면, 대략 최악의 경우 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)인 알고리즘을 설계.

    
    

공간 복잡도

• 알고리즘을 위해 필요한 메모리의 양을 의미한다.

• 공간 복잡도 또한 O(NlogN), O(N^2) 등으로 표기한다.

• 문제에서 제시하는 시간 제한과 메모리 제한은 시간 복잡도와 공간 복잡도를 함께 제한하기 위함이다.

• 코딩 테스트에서 보통 메모리 사용량을 128 ~ 512MB 정도로 제한하기 때문에, 일반적으로 데이터의 개수가 1,000만 단위가 넘어가지 않도록 알고리즘 설계를 해야한다.

• 만약, 리스트의 크기가 1,000만 단위 이상이라면 알고리즘을 잘못 설계했을 가능성이 크다.

시간 측정

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

• 파이썬에서 프로그램 수행 시간을 측정하는 소스 코드는 위와 같다.

• 알고리즘을 설계한 뒤에 시간 복잡도를 경험적으로 증명하고 싶을 때 주로 사용한다.

해당 글은 다음 도서의 내용을 정리하고 참고한 글임을 밝힙니다. 보다 자세한 내용은 아래 책에서 확인할 수 있습니다.
나동빈, ⌜이것이 취업을 위한 코딩 테스트다 with 파이썬⌟, 한빛미디어, 2020, 604쪽