파이썬 시간복잡도와 빅오표기법

시간 복잡도 & 빅오 표기법

알고리즘의 시간 복잡도

좋은 알고리즘이란 무엇일까?

== 효율성이 좋은?

== 성능이 좋은?

== input을 넣은 후 Output이 나오는 시간이 짧은 알고리즘!

알고리즘의 소요 시간 측정하기 - 1

개개인의 컴퓨팅 환경에 따라 같은 알고리즘이라도 측정 시간이 다르다.

환경에 영향을 받지 않는 객관적인 기준이 필요하다.

알고리즘의 소요 시간 측정하기 - 2

객관적 측정을 위해 알고리즘 내부에서 기본연산이 몇 번 일어나는지 살펴본다. == 몇 번의 연산이 일어나는지 확인

기본연산의 총 횟수 == 알고리즘의 소요 시간

def count(word, char):
  total = 0
  
  for i in word:
    if i == char:
      total += 1
  return total

기본연산의 횟수를 구하는 것은 환경에 영향을 받지 않는 객관적인 방법이지만 입력의 개수 에 따라서 시간이 달라지는 문제점이 있다.

예를들어 “apple”에서 “p”라는 단어를 찾는데, 입력된 문장이 “appleapple”이라면 시간이 달라질것이다.

따라서 성능을 측정할 때는 입력을 통일 시켜서 가장 기본 연산이 많이 일어나는 최악의 입력 n개가 들어온다고 가정한다 count("aaaaa", "a")

시간 복잡도(Time Complexity)

문제를 해결하는데 걸리는 시간과 입력의 함수 관계

알고리즘의 수행 시간을 의미

시간 복잡도가 높다 -> 느린 알고리즘

시간 복잡도가 낮다 -> 빠른 알고리즘

빅오(Big-O) 표기법

[개발자 1] : 6n + 4 == O(n)

[개발자 2] : 3n + 2 == O(n)

[개발자 3] : 3n^2 + 6n + 1 == O(n^2)

입력 n이 무한대로 커진다고 가정하고 시간 복잡도를 간단하게 표시하는 것, 최고차항만 남기고 계수와 상수 제거

O(1) (상수복잡도): 단순 산술 계산(덧셈, 뺄셈, 곱셈, 나눗셈) 단순계산

O(logN): 크기 N인 리스트를 반절씩 순회/탐색 이진탐색(Binary Search), 분할정복(Divide & Conquer)

O(N): 크기 N인 리스트를 순회 (count 함수 해당) 리스트순회

O(NlogN): 크기 N인 리스트를 반절씩 탐색 * 순회, 높은 성능의 정렬(Merge/Quick/Heap Sort)

O(N^2): 크기 M, N인 2중 리스트를 순회

O(N^3): 3중 리스트를 순회

O(2^N): 크기 N 집합의 부분 집합

O(N!): 크기 N 리스트의 순열

(일반적 상황에서) 1초가 걸리는 입력 크기

O(N): 1억(기준)

O(logN): 500만

O(N^2): 1만

O(N^3): 500

O(2^N): 20

O(N!): 10

# 합 구하기 
def get_total(n):
  total = 0
  
  for i in range(1, n + 1):
    total += i
  return total
# 이런 경우 n이 높아지면 시간초과가 된다

# 가우스의 합 공식
def get_total(n):
  return(n*(n+1))//2
# 단순계산 O(N)

같은 Output을 만드는 알고리즘이라도 시간복잡도에 따라 성능이 달라질 수 있고 시험에서 정답 여부가 갈릴 수 있다.

또한, 내장 함수, 메서드의 시간 복잡도도 확인할 필요가 있다.

for 문을 한 번만 썼는데도 시간초과가 나는 경우, for문 안에 O(n)의 내장함수를 사용했다면 사실상 이중 for문과 다를 것이 없다.

함수와 메서드에 대한 시간복잡도는 아래의 홈페이지를 참고해보자.

https://wiki.python.org/moin/TimeComplexity

배열 vs 연결리스트

배열(Array)

여러 데이터들이 연속된 메모리 공간에 저장되어 있는 자료구조

• 인덱스를 통해 데이터에 빠르게 접근
• 배열의 길이는 변경 불가능 -> 변경 하려면 새로 생성 해야함
• 데이터 타입은 고정

# C 언어에서 배열 선언
int arr[5] = {70, 80, 20, 100, 90}

[C 언어에서의 배열]

연결 리스트(Linked List)

데이터가 담긴 여러 노드들이 순차적으로 연결된 형태의 자료구조

• 맨 처음 노드부터 순차적으로 탐색
• 연결리스트의 길이 자유롭게 변경 가능 -> 삽입, 삭제가 편리
• 다양한 데이터 타입 저장
• 데이터가 메모리에 연속적으로 저장되지 않음

파이썬의 리스트(List)

배열의 장점(인덱스 접근)과 연결리스트의 장점(가변 길이)을 둘 다 가지고 있음

파이썬 리스트 메서드와 복잡도

1) .append(원소)O(1) : 리스트 맨 끝에 새로운 원소 삽입(리턴값이 없다) 2) .pop(인덱스)O(1) : 특정 인덱스에 있는 원소를 삭제 및 반환(리턴값이 있다)

1. .count(원소)O(N) : 리스트에서 해당 원소의 개수를 반환
2. .index(원소)O(N) : 리스트에서 처음으로 원소가 등장하는 인덱스 반환

3. .sort()O(N Log N): 리스트를 오름차순으로 정렬 reverse() = True를 통해 내림차순으로 정렬 가능

4. .reverse()O(N) : 리스트의 원소들의 순서를 거꾸로 뒤집기

리스트 관련 내장 함수

1. len(iterable) : 리스트 길이(원소의 개수) 반환
2. sum(iterable) : 리스트의 모든 원소의 합 반환
3. max(iterable) : 리스트 원소 중 최대값 반환
4. min(iterable) : 리스트 원소 중 최소값 반환
5. sorted(iterable) : 오름차순으로 정렬된 새로운 리스트 반환, 원본 리스트는 변화 없음
6. reversed(iterable) : 리스트의 순서를 거꾸로 뒤집은 새로운 객체 반환, 원본 리스트는 변화 없음