런타임 분석 설명

Question

설명을 위해. 3 가지 다른 기능을 호출하는 알고리즘이있는 경우. 이 함수들 각각은 logn의 런타임을 가지고있다. 알고리즘의 실행 시간은 bigO (log n)입니다. 맞습니까? f (n) = O (g (n)) 인 bigO의 정의는 모든 n ≥ k에 대해 0 ≤ f (n) ≤ cg (n)가되도록 양의 상수 c와 k가 있음을 의미합니다. c와 k의 값은 함수 f에 대해 고정되어야하며 n에 의존해서는 안됩니다. 이 상황. 우리는 c를 3 함수로 3으로, g (n)을 logn으로 보았을까요?

Answer 1

알고리즘이 이러한 함수를 호출하는 방법에 따라 다릅니다. 알고리즘이

function algorithm(input) { f(input'); // size of input' = O(size of input) g(input''); // size of input'' = (size of input) h(input'''); // size of input''' = O(size of input) }

과 같은 경우 실행 시간은 함수의 알고리즘 호출을 번 실행의 합이다. 따라서, O(log n)에 f, g 및 h이 실행되면 알고리즘은 또한 O(log n) 시간에 실행됩니다.

Answer 2

함수가 f(n)이고 호출하는 함수가 f_1(n), f_2(n) 및 f_3(n)이라고 가정 해 봅시다. T(f(n))도 실행 시간은 f(n)이라고합시다. 어떤 i 들어 f_i(n) 시간 O(log(n)) 실행했다 작동하면

후 그것은 c_i > 0 및 n_i >= 0을가 존재하고, 정의 수단에 의해 이러한 모든 n >= n_i, T(f_i(n)) <= c_i * log(n) 대. 위의 사실에서

는 증거하기 위해 T(f(n))는 그냥 상수 n0 >= 0, c > 0을 찾을 필요도 O(log(n))되도록 모든 n >= n0, T(f(n)) <= c * log(n)합니다.

n0 = max(n_1, n_2, n_3) 및 c = 3 * max(c_1, c_2, c_3)을 선택하면 조건이 완전 채워 지므로 실제로 T(f(n)) = O(log(n))이됩니다. f(n)은 f_1(n), f_2(n)과 f_3(n)을 호출하고 이러한 함수는 각각 정확히 한 번만 호출된다는 것을 알고 있기 때문에 충분합니다.