運行時分析澄清

Question

只是爲了說明。如果你有一個調用3個不同函數的算法。每個函數都有一個logn運行時間。算法的運行時間是否正確？定義bigO爲f（n）= O（g（n））意味着存在正常數c和k，使得對於所有n≥k，0≤f（n）≤cg（n）。對於函數f，c和k的值必須是固定的，並且不能取決於n。對於這種情況。我們可以將c看作是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) }

那麼運行時間運行的功能倍算法調用的總和。因此，如果f,g和h在時間O(log n)上運行，那麼算法也在時間O(log n)中運行。

Answer 2

假設你的功能是f(n)，它所調用的3個功能是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))也O(log(n))，你只需要找到常數n0 >= 0, c > 0，使得對所有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)，並且這些函數中的每一個函數都被調用一次。