algorithm - 大きなO表記でNが2倍になったときの走行回数の比率

Question

Big O表記を使用して、それを学びました

O(f(n)) + O(g(n)) -> O(max(f(n),g(n))

O( f(n) )* O( g(n)) -> O( f(n) g(n))

しかし今、私は入力サイズNの実行時間Tのこの式を持っています

T(N) = O(N^2)  // O of N square

比率を求める必要がありますT(2N) / T(N)

私はこれを試しました

T(2N) / T(N) --> O((2N)^2) /O( N^2)  --> 4

これは正しいです？それとも上記の分割は無効ですか？

Answer 1

T(N) = Θ(N²) (big-theta) であっても、これは機能しません。(big-O について話すつもりはありません。)

c1 * N² <= T(N) <= c2 * N²
c1 * 4 * N² <= T(2N) <= c2 * 4 * N²

T(N) = c_a * N² + f(N)
T(2N) = c_b * 4 * N² + g(N)

c_a と c_b は c1 と c2 の間のどこかで、f(N) と g(N) は N² の small-o です。(G. Bach に感謝します!) c_a、c_b、f(N)、g(N) の両方があらゆる種類のものになる可能性があるため、商が 4 になることを保証するものは何もありません。たとえば、c_a = 1、c_b = 2、および f(N) = g(N) = 0 を取ります。それらを割ると、次のようになります。

T(2N)/T(N) = (2 * 4 * N²)/N² = 8