잔재미코딩

파이썬과 컴퓨터 사이언스(알고리즘) - 알고리즘 복잡도 표현 방법

1. 알고리즘 복잡도 표현 방법

하나의 문제를 푸는 알고리즘은 다양할 수 있음

  • 정수의 절대값은 정수값을 제곱한 값에 다시 루트를 씌우는 방식으로도 계산할 수 있음

여러 알고리즘 중에 어떤 알고리즘이 더 좋을까? - 알고리즘 분석

  • 다양한 알고리즘 중 어느 알고리즘이 더 좋은지를 분석하는 것
    1. 시간 복잡도: 알고리즘 실행 속도
    2. 공간 복잡도: 알고리즘이 사용하는 메모리 사이즈

반복문이 지배합니다.

  • 예:
    • 자동차로 서울에서 부산가기
      1. 자동차 문열기
      2. 자동차 문닫기
      3. 자동차 운전석 등받이 조정하기
      4. 자동차 시동걸기
      5. 자동차로 서울에서 부산가기
      6. 자동차 시동끄기
      7. 자동차 문열기
      8. 자동차 문닫기
생각해보기
위 자동차 서울에서 부산가기에서 가장 총 시간에 영향을 많이 미칠 것 같은 요소는?

마찬가지로, 프로그래밍에서 시간 복잡도에 가장 영향을 많이 미치는 요소는 반복문

  • 입력의 크기가 커지면 커질수록 반복문이 알고리즘 수행 시간을 지배함

알고리즘 성능 표기법

  • O표기법은 알고리즘의 최악의 성능을 표시
    • 가장 많이/일반적으로 사용함
    • 아무리 최악의 상황이라도, 이정도의 성능은 보장한다는 의미이기 때문
  • Ω표기법은 알고리즘의 최고의 성능을 표시
  • θ표기법은 정확한 알고리즘의 성능을 표시

대문자 O 표기법

  • 빅 오 표기법이라고도 부름
  • O(입력)
    • 입력 n 에 따라 결정되는 시간 복잡도 함수
    • O(1), O($log n$), O(n), O(n$log n$), O($n^2$), O($2^n$), O(n!)등으로 표기함
    • 입력 n 의 크기에 따라 기하급수적으로 시간 복잡도가 늘어날 수 있음
      • O(1) < O($log n$) < O(n) < O(n$log n$) < O($n^2$) < O($2^n$) < O(n!)

  • 빅 오 입력값 표기 방법
    • 예:
      • 만약 시간 복잡도 함수가 2$n^2$ + 3n 이라면
        • 가장 높은 차수는 2$n^2$
        • 상수는 실제 큰 영향이 없음
        • 결국 빅 오 표기법으로는 O($n^2$) (서울부터 부산까지 가는 자동차의 예를 상기)
프로그래밍 연습
1부터 n까지의 합을 구하는 알고리즘 작성해보기
In [56]:
def func(n):
    count = 0
    for num in range(1, n + 1):
        count += num
    return count

func(10)
Out[56]:
55

실제 알고리즘을 예로 각 알고리즘의 시간 복잡도와 빅 오 표기를 알아보자

알고리즘1: 1부터 n까지의 합을 구하는 알고리즘1

  • 합을 기록할 변수를 만들고 0을 저장
  • n을 1부터 1씩 증가하면서 반복
  • 반복문 안에서 합을 기록할 변수에 1씩 증가된 값을 더함
  • 반복이 끝나면 합을 출력
In [16]:
def sum_all(n):
    total = 0
    for num in range(1, n + 1):
        total += num
    return total
In [17]:
sum_all(100)
Out[17]:
5050

알고리즘2: 1부터 n까지의 합을 구하는 알고리즘2

  • $\frac { n (n + 1) }{ 2 }$
In [20]:
def sum_all(n):
    return int(n * (n + 1) / 2)
In [21]:
sum_all(100)
Out[21]:
5050

알고리즘1 시간 복잡도 구하기

  • 1부터 n까지의 합을 구하는 알고리즘1
    • 입력 n에 따라 덧셈을 n 번 해야 함 (반복문!)
    • 그래서 빅 오 표기법으로는 시간 복잡도는 O(n)
  • 1부터 n까지의 합을 구하는 알고리즘1
    • 입력 n이 어떻든 간에, 곱셈/덧셈/나눗셈 하면 됨 (반복문이 없음!)
    • 그래서 빅 오 표기법으로는 시간 복잡도는 O(1), 상수가 됨

알고리즘2: 리스트 데이터에서 동일한 이름을 가진 이름 추출하기

  • set 사용하지 않고, 구현하기
In [29]:
names = ['Dave', 'David', 'Anthony', 'Andy', 'Dave']

프로그래밍 연습
이름을 리스트 데이터로 가진 리스트 변수를 넣으면, 해당 변수에서 동일한 이름을 가진 중복 리스트 데이터를 삭제한 리스트 출력하기
예:

names = ['Dave', 'David', 'Anthony', 'David', 'Dave']
find_same_name(names)
출력: ['Dave', 'David', 'Anthony']
</div>

참고 enumerate

  • for index, name in enumerate(name_list):
  • name_list 리스트 변수 길이 만큼 반복: 0 ~ (len(name_list) - 1)
  • 이 때 index에는 인덱스번호가 0 ~ (len(name_list) - 1), name 에는 해당 인덱스 번호에 저장된 리스트 데이터가 저장됨
In [57]:
def find_same_name(name_list):
    for index, name in enumerate(name_list):           # 반복문에 주의!
        for index2 in range(index + 1, len(name_list)):   # 반복문에 주의!
            if (name == name_list[index2]):
                del name_list[index2]

    return name_list
In [63]:
def find_same_name(name_list):
    for index, name in enumerate(name_list):
        for index2 in range(index + 1, len(name_list)):
            if (name == name_list[index2]):
                del name_list[index2]
    return name_list
In [ ]:
In [64]:
name_list = ['Dave', 'David', 'Anthony', 'David', 'Dave']
find_same_name(name_list)
Out[64]:
['Dave', 'David', 'Anthony']

알고리즘2 시간 복잡도 구하기

  • 반복문이 중첩
    • for name in name_list
    • for index in range(name_index, len(name_list))
  • 리스트 사이즈가 3 일때, (중복되는 이름이 없는 최악의 상황을 가정)
    • 리스트 인덱스 0에 대해서는 1, 2 와 비교 (n - 1)
    • 리스트 인덱스 1에 대해서는 2 와 비교 (n - 2)
    • 결국 일반화 시키면, n (n - 1) / 2 --> $\frac { n^2}{ 2 } - \frac { n}{ 2 }$
    • 여기서 가장 높은 차수만 빼고 상수와 나머지 차수를 다 제외 하면!
    • $n^2$
    • 그래서 빅 오 표기법으로는 시간 복잡도는 O($n^2$), 이 됨