시간 복잡도&빅오 표기법

🙄좋은 알고리즘이란?

효율성? 성능?

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

시간 복잡도

• 알고리즘의 소요 시간 측정
  • 기본 연산이 몇 번 일어나는지(적게 걸릴수록)
  • 기본 연산의 총 횟수 == 알고리즘의 소요 시간

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

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

빅오(Big-O)표기법

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

n이 커지면 시간 복잡도가 커지므로 수학 공식을 사용해 간단하게 해준다

-> 단순 계산이 되므로 시간복잡도가 O(1)이 됨

• O(1): 단순계산 -> a + b, 100 * 200
• O(logN): 이진탐색(Binary Search), 분할정복(Divide & Conquer)
• O(N): 리스트 순회, 1중 for 문
• O(NlogN): 높은 성능의 정렬(Merge/Quick/Heap Sort)
• O(N^2): 2중 리스트 순회, 2중 for 문
• O(N^3): 3중 리스트 순회, 3중 for 문
• O(2^N): 크기가 N인 집합의 부분 집합
• O(N!): 크기가 N인 순열

O(1)보다 O(n)이 더 많음

리스트[]

배열 vs 연결리스트

배열

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

• 인덱스를 통해 접근
• 배열의 길이 변경 불가능 -> 길이 변경하고 싶으면 새로 생성
• 데이터 타입 고정

연결리스트

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

• 처음 노드부터 순차적 탐색
• 길이 자유롭게 변경 가능
• 테이터 타입 자유로움

파이썬 리스트의 메서드

O(1) (인덱스가 없을 때)

1. .append(원소) 리스트 맨 끔에 새로운 원소 삽입 => return 값 없음
2. .pop(인덱스) 특정 인덱스에 있는 원소를 삭제 및 변환 => return 값이 있음

a = [1,2,3,4,5]  #len(a) => O(1) 
a. append(6)
print(a) #[1,2,3,4,5,6]   => return 값 없음
a = [1,2,3,4,5]
b = a.pop()
  
print(a)   #[1,2,3,4]
print(b)   #5    => return 값 있음

3. .count(원소) 리스트에서 해당 원소의 개수를 반환
4. .index(원소) 리스트에서 처음으로 원소가 등장하는 인덱스 반한
5. .sort() 리스트를 오름차순으로 정렬 -> reverse = True로 내림차순 정렬 가능
6. .reverse() 리스트의 원소들의 순서를 거꾸로 뒤집기

리스트 관련 내장함수

1. len(iterable) O(1)
2. sum() O(n)
3. max() O(n)
4. min() O(n)
5. sorted() 공간을 덜 생각하고 효율을 극대화
6. reversed()

=> 이 함수의 시간복잡도 알아보기