計算時間T（n）和帶有無限循環的Big-O

我很困惑如何創建函數T（n）來測量嵌套無限循環的計算時間。下面是代碼：計算時間T（n）和帶有無限循環的Big-O

x=1; 
for(int i = 0;i<n-1;i++){ 
    for(int j = 1; j<=x; j++){ 
     cout << j << endl; 
     x*=2; 
    } 
}

所以內循環將永遠繼續下去，而且我堅持努力打造代表其計算時間的函數。我寫過它的計算時間是T（n）= [Summation i = 0直到（n-2）]（2^j）。 2^j表示內部循環中x的當前值爲j的值。在和我的同事討論這個問題之後，我們絕對同意計算時間肯定不取決於n的值。由於循環是無限的，我們也可能會完全過度考慮這一點，並且根本無法表達其計算時間。任何幫助是極大的讚賞。

來源

2011-10-11 whittenc

我徹底糊塗了。你想要一個無限循環的運行時間？這是無限的。順便說一句，外環是無關緊要的，因爲內環永遠不會完成。另外，它在實踐中可能不是無限的，因爲如果它是一個整數類型，x將最終包裝。 –

時間複雜度僅對終止的算法有意義。 –

是的，我知道外部循環是無關的，是的，我知道設計一個這樣的計算算法是沒有意義的，但我需要嘗試:) – whittenc

那麼，在現實世界中，你不會因爲明顯的原因得到答案，但是在數學中......爲什麼不呢。

我寫下了函數的時間等式：

T(n) = n-1 * T(X)

T(X)是內部循環的時間。我會花費它：X1 =的x初始值（在此情況下1）

T(X) = T(X1 * 2) + 1 = T(X1 * 4) + 2 = ... = T(X1 * 2^j) + j

該循環的結束條件是當j >= X1 * 2^j + 1，所以我們想解決：

j >= X1 * 2^j -> j = 2^j -> j <= log2(j).

上面方程式在這個自然數集範圍內沒有解，但在整數集中，它很容易用-1（實際上是小於0的任何整數）解決。

因此，T(n)的時間複雜度爲(n-1) * (-1) = 1 - n。

我不知道這有什麼用處，但我希望它能爲你解決問題。

來源

2011-10-22 06:31:20 Neowizard

上帝不！一般來說，對數是* not *對任何小於或等於'0'的參數都是定義的。 – andr

日誌沒有在0以下定義，但是我看到它的方式，您無法定義無限循環的時間複雜性。 – Neowizard

好吧，那麼你應該寫這個，而不是寫一個數學錯誤的答案！這與你的第一段尤其矛盾：*但是在數學中......爲什麼不是*。更好的答案是'T（n）= + inf'，因爲它肯定不會引起OP的混淆。 – andr

算法複雜度僅針對由（最常接受的）定義必須終止的算法定義。這個過程並沒有終止（除了Marcelo筆記中的「在實踐中」，即作爲一個真機上的程序，或者理論上用理論上的圖靈機和一個無限大的磁帶並且一直在世界上），所以不是算法。所以它沒有「算法時間複雜度」。

試圖確定非算法的算法複雜性是徒勞的練習，因爲試圖將其運行時間表示爲多項式（如果它是無限過程的話）。

來源

2013-01-14 00:29:58 wwwayne

真正無限循環的大O複雜度是undefined。這裏的原因：

的大O符號的定義說：

f(N) = O(g(N))當且僅當f(n) <= |M g(n)|對於某一常數M，併爲所有n >= n0

但是，前提是f(n)和g(n)是實數的一些子集上的函數。

在無限循環的情況下，f(n)的值是「無窮大」，它不是實數。因此，我們不能將Big O表示法應用於數學意義上的問題（真正的無限循環）。

（上Big O Notation指出這更正式的維基百科頁面。）

來源

2015-10-11 05:37:39

計算時間T（n）和帶有無限循環的Big-O

回答

相關問題