1樓：「已登出」
我覺得如果乙個演算法的耗時和「問題規模N」的關係是正切函式的話，那麼不如說是這個「時間複雜度」或者「問題規模」定義得有問題。
牛頓迭代法就可以作為乙個例子。比如乙個函式，某些點收斂速度很快，某些點收斂速度很慢，某些點不收斂，那這個時候你去定義時間複雜度就沒什麼意義了，斂散性和收斂速度才是最重要的。
2樓：
這個事情是不講道理的，我來這裡說道說道。
注意到這裡說的是 而不是 或者 之類的。回顧一下大O漸進記號的定義：
0, x_0, \text \forall x \geq x_0, |f(x)| \leq M|g(x)|." eeimg="1"/>
注意到由於有絕對值，所以 為負數好像也沒啥關係。
考慮到乙個合理的演算法至少擁有不低於某常數的執行時間， 0" eeimg="1"/>。
而 是週期函式，在接近 的時候值趨近於0。因為 可以任意大，這樣就顯然不存在乙個 使得對任意充分大的 都有 ，因為 可以任意小。
即使限制 只能為正整數 ，也可以知道，由於有理數可以逼近無理數，那麼 0, \exists n, k \in \mathbb, \text |n - k\pi| < \epsilon" eeimg="1"/>，同樣可以使得 任意趨近0。
如果考慮的是 的話，這個就變得不一樣。因為 是無界的，而且 記號同時限制了上下界，這這個彷彿是在說，演算法的執行時間隨著問題規模忽大忽小的變化，聽起來也不是很講道理。
而那個加1一直加到小於 的最大整數，這個 實在不算是個問題規模的描述。
Reference：
Big O notation - Wikipedia
關於演算法的時間複雜度
水dong方塊 演算法時間複雜度分析 選取演算法中一種基本 主要的原操作 取自最深層次迴圈體內的語句 以它重複操作的次數Tn衡量演算法執行時間 n是處理的資料的規模。如果存在兩個常數c1，c2 時則稱Tn和fn 有相同的漸進複雜度 記作 Tn na than 求解演算法的時間複雜度的具體步驟是 找出...
位數確定指令複雜度是否存在上下限
fred fu 瀉藥，這方面了解其實有限，談點自己的看法吧。按我的理解題主的意思是同樣64位或者32位，指令集的複雜度是否存在上下限。我認為是存在的，但這一上限或者下限是因實際使用功能和設計思路而決定，不是理論決定，因為畢竟產品最終都是要落到使用上，不同的用途有其各自的上下限。當你精簡或者複雜到一定...
如何證明Manacher演算法的時間複雜度是O n
Manacher演算法本身的原理就不贅述了，提供一點關於時間複雜度的個人見解。首先for loop裡面套乙個while loop，直覺非常像 但前提是for loop本身的次數，和while loop本身迴圈的複雜度都是 真的是這樣嗎？未必。為什麼未必呢？想想Manacher演算法的核心思想是什麼，...