2. Algorithm Analysis
Created: October 22, 2022 10:25 PM
Our two most important tools are (1) the RAM model of computation and (2) the asymptotic(점근선의) analysis of worst-case complexity.
2.1 The RAM Model of Computation
Machine-indepenent 알고리즘 디자인은 RAM(Random Access Machine)이라고 하는 가상의 컴퓨터에 의존적이다. 이 컴퓨테이션 모델에서의 컴퓨터는 다음과 같다.
- simple operation (+, *, –, =, if, call) 은 one time step이 걸린다.
- Loops 와 subroutines는 simple operations가 아니다. single-step operations의 composition이다.
- 하나의 memory access는 one time step이 걸린다. 그리고 memory는 필요한 만큼 가지고 있다. RAM model은 가져오려는 대상이 cache에 있거나 disk에 있다는 것을 알지 못한다. (어디에 있느냐를 상관하지 않는다.)
RAM model에서 run time은 주어진 문제에 알고리즘이 걸리는 step의 수로 계산한다.
2.1.1 Best, Worst, and Average-Case Complexity
to understand how good or bad an algorithm is in general, we must know how it works over all instances.
- The worst-case complexity of the algorithm is the function defined by the
- maximum number of steps taken in any instance of size n.* This represents
the curve passing through the highest point in each column. - The best-case complexity of the algorithm is the function defined by the minimum number of steps taken in any instance of size n. This represents the
curve passing through the lowest point of each column. - The average-case complexity of the algorithm, which is the function defined
by the average number of steps over all instances of size n.
The worst-case complexity proves to be most useful of these three measures in practice.
왜냐하면 가장 쉬워서. 복잡성을 다 제외하고 그냥 worst case만 생각한다.
2.2 The Big Oh Notation
The best, worst, and average-case 시간 복잡도는 다음과 같은 경향 때문에 까다롭다.
- Have too many bumps: binary search는 n = 2ᵏ-1 일 때 빠르다. 디테일은 중요하지 않지만 정확한 시간 복잡도 함수는 매우 복잡해질 수 있고, 다음 그림과 같은 bump들이 생길 수 있다.
- Require too much detail to specify precisely: 정확하게 표현하기 위해서는 디테일한 사항이 필요하다. 하지만 이런 디테일은 중요하지 않은 정보이다. 예를 들어 T(n) = 12754n² + 4353n + 834lg₂n + 13546 같은 정확한 worst-case를 수행하는 것은 어렵지만 시간이 n 제곱으로 늘어난다는 것 이오의 정보를 제공해주지 않는다.
Big Oh notation의 정의는 다음과 같다.
- f(n) = O(g(n)) means c · g(n) is an upper bound on f(n). Thus there exists some constant c such that f(n) is always ≤ c · g(n), for large enough n (i.e. ,n ≥ n0 for some constant n0).
- f(n) = Ω(g(n)) means c · g(n) is a lower bound on f(n). Thus there exists some constant c such that f(n) is always ≥ c · g(n), for all n ≥ n0.
- f(n) = Θ(g(n)) means c1 · g(n) is an upper bound on f(n) and c2 · g(n) is a lower bound on f(n), for all n ≥ n0. Thus there exist constants c1 and c2 such that f(n) ≤ c1 ·g(n) and f(n) ≥ c2 ·g(n). This means that g(n) provides a nice, tight bound on f(n).
The Big Oh notation provides for a rough notion of equality when comparing functions. It is somewhat jarring to see an expression like n2 = O(n3), but its meaning can always be resolved by going back to the definitions in terms of upper and lower bounds. It is perhaps most instructive to read the “=” here as meaning one of the functions that are. Clearly, n2 is one of functions that are O(n3).
2.3 Growth Rates and Dominance Relations
each operation takes one nanosecond (10−9 seconds).
The following conclusions can be drawn from this table:
- 모든 알고리즘은 n = 10 일 때 대략 걸리는 시간이 같다.
- n! 알고리즘에 대해 n > 20 일 때 러닝 타임은 쓸모없어진다.
- 실행 시간이 2ⁿ인 알고리즘은 더 큰 작동 범위를 가지지만 n > 40에 대해서는 실용적이지 않다.
- 실행 시간이 n²인 2차 시간 알고리즘은 약 n = 10,000까지 사용 가능하지만 더 큰 입력에 따라 빠르게 악화된다. n > 1,000,000 일 때는 실용적이지 못하다.
- linear-time과 nlogn 알고리즘은 one billion 까지 실용적이다.
- O(log n) 알고리즘은 상상 가능한 n에 대해 시간이 거의 걸리지 않는다.
2.3.1 Dominance Relations
faster-growing 함수가 slower-growing 함수를 지배한다고 얘기한다. f와 g가 다른 클래스로 분류될 때 (i.e., f(n) = Θ(g(n))), g가 f를 지배한다고 한다. 이를 g>>f 라고 쓴다.
n! >> 2ⁿ >> n³ >> n² >> n log n >> n >> log n >> 1
2.4 Working with the Big Oh
2.4.1 Adding Functions
두 함수의 합은 dominant 함수가 지배한다.
2.4.2 Multiplying Functions
when two functions in a product are increasing, both are
important. The function O(n!log n) dominates n! just as much as log n dominates
In general,
O(f(n)) ∗ O(g(n)) → O(f(n) ∗ g(n))
Ω(f(n)) ∗ Ω(g(n)) → Ω(f(n) ∗ g(n))
Θ(f(n)) ∗ Θ(g(n)) → Θ(f(n) ∗ g(n))