T (N) = O (2^n) 일 때 증가하는 CPU 속도의 효과는 어떻게 계산합니까?

Question

다음 시나리오가 제시되었습니다. 알고리즘 A는 O (2^n)입니다. CPU를 10 배 더 빠르게 선택할 수도 있고 알고리즘 B (O (n^2))를 선택할 수도 있습니다. 분명히 알고리즘 B를 선택 하겠지만 추론을 통해서만이 알고리즘을 수학적으로 정당화해야합니다.

나는 알고리즘 B가 (2^n/n^2) 배 더 큰 문제를 풀 수 있다고 들었다. 이것은 내가 이해합니다. 여태까지는 그런대로 잘됐다.

그러나 더 빠른 CPU로 문제 (n + log 10) (약 n + 3)를 풀 수 있다고합니다.

(2^n/10)에서 (n + log 10)을 얻는 방법은 무엇입니까?

Answer 1

문제를 해결하는 데 걸리는 시간은 작업량을 CPU 속도로 나눈 값으로, 첫 번째 알고리즘의 경우 (2^n)/속도로 표현할 수 있습니다. 속도에 10을 곱하면 (2^n)/(10 * 속도)가됩니다. "X가 더 큰 문제를 풀 수 있습니다"라는 말은 "더 큰 문제를 같은 시간에 해결할 수 있습니다."라는 의미입니다.

그래서 (2^n)/속도 = (2^(n + 큰))/(10 * 속도). 대수적으로 더 큰 것을 풀면 더 큰 것으로 끝납니다 = 속도는 로그 10이됩니다.