這個循環的時間複雜度是多少？

Question

for(i=0; i < n; i * = 25) 

至於我想的複雜性無法確定。 迭代永遠不會繼續，所以循環基本變成無限循環。

Answer 1

正如評論中所述，該循環僅終止於n ≤ 0。對於其他所有n，程序不會終止。

我想你不想談的複雜性，如果你有什麼事情，永遠不會終止，因爲複雜性被用來獲取大的投入運行時間的想法，並比較算法。

你甚至不能說你的代碼是一種算法，因爲算法的定義通常包含，它必須終止。

如果你被要求寫在大澳的東西有看看這個方法不止一種。

1. 算法永遠不會終止，所以它是無限的操作，你不能找到一個常數c與∞ < c⋅f(n)爲n < ∞功能f(n)（多項式或指數），所以它應該是O(∞)。
   這由big-o的正式定義支持。
2. 如果你看一下執行的操作的數量的變化，如果您雙擊輸入，n → 2n你看到的，執行的操作的數量不會改變，所以也許O(1)也是可能的。
   這由重複公式T(n) = T(n-1)支持。最後你必須定義T(1)是什麼。複雜性與小的或特定的輸入無關，所以也許可以定義T(1) = O(1)。

兩種方式都表示，運行時間不取決於輸入，但第二個主要是哲學，第一個應該是首選。

但正如我在開始時說：你不想談上永遠不會終止（或只爲不相關的情況下）代碼的複雜性。