키워드
Time Complexity
Space Complexity
Drop the Constants
Drop the Non-Dominant Terms
Multi-Part Algorithms: + VS. *
Amortized Time
Log N Runtimes
Recursive Runtimes
모든 상황에서 효율이 좋은 알고리즘이란 것은 존재하지 않는다.
complexity를 구할 때는 guess하면 안된다. 항상 언제나 derive해야 한다.
Big O는 best case, worst case, expected case로 구분해서 구할 수 있으나 유의미한 것은 best를 제외한 2가지 case다.
drop constant
constant를 버리는 것이 부정확한 해석이라고 오해할 수 있는데 아니다. 정확하게 따지려면 한도 끝도 없어서 필요에 의해 어느 정도 단순화할 필요가 있다.
drop non-dominant terms
merge sort O(n logn)
quick sort
임의의 수를 pivot으로 선택하고 그것을 기준으로 숫자들을 2개의 그룹으로 나눈다.
각각의 그룹에서 pivot을 선택하고 2개의 그룹을 나누는 것을 반복한다.
x! > 2^x > x^2 > x logx > x > logx > 1
Recursive Runtimes : O(branches ^ depth)
examples & exercises
3번 complexity를 구하는 방법은 여럿이다. 다양한 방법이 있는 것을 알아두는 것은 좋지만 그것들을 모두 내 것으로 만들 필요는 없다.
7번 식을 구성하는 부분들 중 언급되지 않은 관계의 것들은 평가하지 않는다.
8번 개인적으로 어렵다고 생각하는 문제
9번 complexity를 구하는 방법은 여럿이다.
10번 빅오는 worst case의 time complexity를 구하는 것이다.
12번 2차 풀이 때도 틀림ㅠ
https://www.codentalks.com/t/topic/6556
https://blog.naver.com/mkzzang0928/222319770961
13번 balanced인 경우 depth가 logN이 되는 것이다. balanced가 보장되지 않았다면 그냥 n으로 두면 된다.
14번 그냥 차분히 잘 분석하면 왠만한 문제는 무리없이 풀 수 있다.
additional questions
- 특정 수를 계속 일정하게 나눠가는 구조라면 그 구조는 O(log n)이라고 볼 수 있다.
