用大O表示算法時間複雜度的歧義

ok, 長話短說，看一下這個函數的時間複雜度是多少？

顯然，這個函數輸入x，然後函數就循環x次，那就是<code>o(n)</code>咯。

此題的來源是考研408裡的一道選擇題，并做了簡化：

此題問時間複雜度是多少，顯然，命題人希望的答案是<code>o(根号n)</code>。

但事實上，真這麼簡單麼？

再來看這個函數：

對于<code>foo3</code>，應該沒有争議，時間複雜度是<code>o(n)</code>。

但是顯然，這兩個函數輸入的資料量完全不一樣，并且實際在機器上運作所耗費的時間也完全不同：<code>foo1</code>隻要輸入一個大的整數，運作的時間就會比輸入上億規模數組的<code>foo3</code>還慢。它們真的都是<code>o(n)</code>的時間複雜度？顯然<code>foo1</code>的時間複雜度應該遠高于<code>foo3</code>啊。

看到這裡，肯定開始覺得沖突和疑惑了，再舉個例子，讓你更糾結。

素數判定問題是一個已知的np-hard問題，求解這個問題的一個直覺算法是：

如果<code>foo1</code>的時間複雜度是<code>o(n)</code>的話，<code>isprime</code>的複雜度也毫無疑問應該是<code>o(n)</code>。

ok，一個np-hard問題就這麼輕易地被多項式時間算法解決了，<code>p = np</code>，圖靈獎誕生了！

其實，引起上述悖論的根源，在于我們使用大o表示法來表示算法時間複雜度時經常忽略的那個參數“n”的定義。在提到<code>o(n), o(log(n))</code>時，參數n的定義到底是什麼？

認為<code>foo3</code>函數的時間複雜度是<code>o(n)</code>，這裡的n指的是輸入的長度。而如果認為<code>foo1</code>的時間複雜度也是<code>o(n)</code>，那麼這裡的n其實指的是輸入的值了。而此時輸入的長度和值之間，存在<code>2^n</code>的關系。如果強行讓n表示為輸入的數的二進制長度，那麼說<code>foo1</code>函數的時間複雜度是<code>o(2^n)</code>也就不難了解了。

那麼，大o表示法下，這個n到底表示什麼意思，有一個确切的定義麼？

in computer science, the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the length of the string representing the input.

是以，嚴格來說，n應該取輸入的“長度”，而不是輸入的“值”。

不要懷疑了，大o表示法的n指的就是輸入的長度。在此前提下，你是否開始認同<code>foo1</code>的時間複雜度是<code>o(2^n)</code>了？

但是等等，為什麼是一定是2的指數級？又沒規定所有計算機都必須是二進制表示的。如果是十進制（事實上第一台計算機就是十進制）表示的呢？譬如17，在十進制下，“長度”是2，二進制下，“長度”就成了5。而我們讨論算法的時間複雜度時，談論的是算法自身的性質，而不會依賴于具體實作，這個函數的時間複雜度為什麼不能是<code>o(10^n)</code>？

造成這個沖突的根源在于，時間複雜度的定義是輸入字元串的長度，但用什麼“編碼方式”來表示輸入卻沒有指定。

編碼不一定指的是字元串編碼，7、七、柒、seven、Ⅶ等等都是對抽象數字“7”的一種編碼。而算法的輸入用不同方式編碼表示的長度肯定不同。

極端一點，如果用一進制來編碼，4就是<code>1111</code>，那麼這種情況下<code>foo1</code>的時間複雜度還真就是<code>o(n)</code>了！

... since computational complexity measures difficulty with respect to the length of the (encoded) input, this naive algorithm is actually exponential. it is, however, pseudo-polynomial time.

...

the distinction between the value of a number and its length is one of encoding: if numeric inputs are always encoded in unary, then pseudo-polynomial would coincide with polynomial.

看！真相大白！

學過計算理論的同學應該在最開始就一眼看出了這是一個“僞多項式時間”的問題。如果真正了解這個詞，這個問題也就不會讓人産生困擾了。

是以，最後，<code>foo1</code>這個“僞多項式時間”算法的複雜度用大o表示法到底是多少？

<code>o(n), o(2^n)</code>，都對又都不對，取決于對輸入n的編碼，如果采用不符合直覺的unary numeral system（一進制），那麼得到的就是符合直覺的<code>o(n)</code>，而如果采用符合直覺的的二進制或十進制，那麼時間複雜度就是指數級。

我們平時張口即來的算法時間複雜度其實是有歧義、不完備的，稍加思考就會發現前文介紹的那種沖突。是以，在這種情況下，最好還是尊重大部分的人的常識比較好。

本文看似出了一道無意義的題，最終也沒有得到一個确切的答案。但在思考的過程中拓展認知的局限，才是真正有意義的事情。