[TIL] 자료구조 220530

알고리즘을 비교할 때 가정해야 하는 몇 가지 가정들이 존재

1. Input >=0 : 항상 들어오는 Input 값은 0보다 크거나 같다. 따라서 복잡도도 0보다 크거나 같다.
2. Functions do more work for more input : Input이 많으면 함수는 더 많이 작업한다.
3. Drop all constants : 시간복잡도에서 상수는 무시한다
(ex 3n 과 n은 같은 시간복잡도를 갖는 것으로 판단)
4. 낮은 차수의 항은 무시한다 : 다양한 차수 항을 갖는 경우 (ex. n^3 + n^2 + n + 5) n^3 만 고려.
5. 로그에서 밑은 무시한다 : math.log(2) = ln(2)
6. 2n = O(n) => 2n 은 O(n)이란 집합에 원소이다

1, c - constant time
log n - trees
n - once per item
n^2 - comparing all v all (ex. bubble sort)
n! - traveling sales problems (외판원 문제)