[코딩테스트 합격자 되기 03] 알고리즘 효율 분석 : 시간복잡도와 빅오 표기법

알고리즘 효율 분석

시간복잡도란?

• 알고리즘의 성능을 나타내는 지표
• 입력 크기에 대한 연산 횟수의 상한
• 알고리즘이 실행되는 제한 시간과 관련 
• 낮으면 낮을수록 좋다

알고리즘 수행 시간을 측정하는 방법

• 절대 시간을 측정하는 방법 
  
  • 실행 후 결과가 나올 때 까지의 시간을 측정 
  • 프로그램 실행 환경에 따라 달라질 수 있어 활용이 제한
• 시간 복잡도를 측정하는 방법
  • '연산 횟수' 와 연관
  • 최신(best), 보통(normal), 최악(worst) 의 경우로 나뉜다. 
  • 점근적 표기법 : 입력 크기에 따른 연산 횟수의 추이를 활용해 시간 복잡도를 표현하는 방법 = 어떤 함수의 증가하는 추세를 표현하는 표기법
• 빅오 표기법
  
  • 최악의 경우에 대해 시간 복잡도를 표현하는 방법
  • 연산 횟수가 f(x) 라고 할 때 함수의 최고차항을 남기고 계수를 지워 O(...) 와 같이 표기하면 된다
    => 시간복잡도 식에서 최고차항 이외의 값들을 2차원 그래프에서 표현해보면 최고차항 이외의 값들은 무시할 수 있을 정도로 작아지기 때문에 최고차항만 남긴다

시간복잡도	N의 가용 범위
O(N!)	10
O(2^N)	20~25
O(N^3)	200~300
O(N^2)	3,000~5,000
O(NlogN)	100만
O(N)	1,000~2,000만
O(logN)	10억

 
 
 

Q&A

1. 시간 복잡도란 무엇인지 정의하고, 왜 알고리즘의 성능 평가에 중요한지 설명하세요.
시간복잡도는 주어진 알고리즘이 수행되는 데 필요한 시간을 입력 크기( n)에 대한 함수로 표현한 것. 시간 복잡도는 알고리즘이 처리해야 할 입력 데이터의 크기가 커짐에 따라, 해당 알고리즘이 얼마나 더 오래 걸릴지를 나타내는 중요한 지표이다.

2. 빅오 표기법이 무엇인지 설명하고 알고리즘의 시간복잡도를 표현할 때 빅오 표기법이 사용되는 이유를 설명하세요.
- 최악의 경우 분석 : 빅오 표기법은 입력 크기가 매우 커질 때, 즉 최악의 경우에 대해 알고리즘의 성능이 어떻게 되는지를 설명한다.
- 최고차항을 남기고 계수를 지워 표기하는 특징: 빅오 표기법은 가장 중요한 항목에 초점을 맞추기 때문에, 복잡한 수학적 수식을 단순화하여 표현할 수 있다. 예를 들어, 시간 복잡도를 나타낼 때 상수나 낮은 차수의 항을 생략하여 표현한다.
 
3. 빅오 표기법에서 최악의 경우를 고려하는 이유는 무엇인가요?
- 최악의 경우를 고려함으로써 모든 상황에서 알고리즘이 어떤 입력에 대해서도 일정 시간 안에 실행될 것이라는 보장을 제공한다. 예상치 못한 상황에서 알고리즘이 매우 비효율적으로 동작하는 것을 방지하기 위해 최악의 경우를 기준으로 성능을 평가한다.

4. 빅오 표기법을 사용할 때의 한계점 및 오해
한계점 및 오해:
- 상수 및 낮은 차수 항 무시:
빅오 표기법에서는 가장 큰 차수만을 고려하기 때문에, 실제 성능 평가에서 중요한 상수 항이나 낮은 차수 항을 무시하는 경우가 있다. 이는 이론적으로는 효율적인 알고리즘이지만, 실제 환경에서는 덜 효율적일 수 있다.

- 최악의 경우만 고려:
빅오 표기법은 최악의 경우를 기준으로 하므로, 평균적인 경우나 최선의 경우에 대한 정보를 제공하지 않는다. 최악의 경우보다 더 좋은 성능을 보이는 알고리즘이 많기 때문에, 이 점을 고려하지 않으면 잘못된 결정을 내릴 수 있다.

- 공간 복잡도 고려 부족:
빅오 표기법은 주로 시간 복잡도에 초점을 맞추지만, 일부 알고리즘에서는 공간 복잡도(메모리 사용량)가 더 중요한 요인이 될 수 있다. 이 경우, 빅오 표기법만으로는 알고리즘의 전반적인 효율성을 평가하는 데 한계가 있을 수 있다.

- 환경에 따른 성능 차이: 빅오 표기법은 하드웨어나 프로그래밍 언어의 특성을 고려하지 않기 때문에, 같은 알고리즘이라도 다른 환경에서 다르게 동작할 수 있다. 이런 차이는 빅오 표기법으로는 설명할 수 없다.
 
 

다음 코드의 시간복잡도를 빅오 표기법으로 나타내세요.

O(n)

def example_function_1(n):
    for i in range(n):
        print(i)

 
 
O(n^2)

def example_function_2(n):
    for i in range(n):
        for j in range(n):
            print(i, j)

 
 
O(n)

def example_function_3(n):
    for i in range(n):
        print(i)
    for j in range(10):
        print(j)

 
 
O(2^n)

def fibonacci(n):
    if n <= 1:
        return n
    else:
        return fibonacci(n-1) + fibonacci(n-2)

 
 
O(logn)

def example_function_3(n):
    i = n
    while i > 1:
        i = i // 2
        print(i)

---

 
 
ref : 코딩테스트 합격자되기 - 파이썬 편

https://wikidocs.net/222560

[되기] 코딩 테스트 합격자 되기 - 파이썬 편(~179스택까지)