是什麼小於n是log n？

Question

考慮問題有兩種解決方案。

1. 執行N/2倍，即。如果n = 100，則執行50次
2. 以n次sqrt執行，即。如果n = 100，則執行10次。

這兩種解決方案都可以稱爲O（log N）？

如果是這樣，則存在的N和N/2之間的sqrt巨大的差異。

如果我們不能說O（日誌N），那麼我們可以說，這是N？

但問題是這兩者之間的差異率。通過下面的圖片算法應該出現在這些東西之中，這些解決方案將在哪些方面出現？

請幫我在這。

Answer 1

考慮三種情況。

1. 執行n/2次。這意味着每一個我們通過因子100，通過100

2. 執行sqrt(n)倍的因子的執行時間的增加加N時間。這意味着每次我們將n增加100倍，執行時間增加10倍。

3. 執行log(n)次。這意味着每次我們將n增加100倍，執行時間就會增加一個常量。

不，這三件事情甚至都沒有接近。第一個比第二個糟糕得多。第三個比第二個好得多。

Answer 2

他們都不是O(logn)

這裏是O(logn)一個例子，Binary search algorithm

Answer 3

最好的算法是，你有數據的最佳算法。如果你不知道你有什麼數據，請考慮大量的數據，比如n = 10億。你會選擇O（31623）還是O（5000000000）？繪製比較圖並找到您的數據大小。

如果您的數據集是n = 4，那麼任一算法都是相同的。如果您瞭解細節，由於它執行的操作，實際上可能需要較長的時間才能執行sqrt（n）算法。

你可以有O（1）這是最快的。一個這樣的例子是查找哈希映射，但是你的內存大小可能會受到影響。所以你應該考慮空間限制和時間限制。

您也在誤解和過分分析複雜性分類。 O（n）算法不是用正好n個操作執行的算法。任何常數乘數不會影響分類的順序。問題增長時，操作次數的增長非常重要。考慮兩種搜索算法。

A) Scan a sorted list sequentially from index 0 to (n-1) to find the number. 

B) Scan a sorted list from from index 0 to (n-1), skipping by 2, and backtracking if necessary. 

顯然需要至多n個操作，和B需要N/2 + 1的操作。然而他們都是O（n）。你可以說算法B更快，但我可以在我的機器上運行它，速度是它的兩倍。所以複雜性是一個普通的階級，人們不應該對操作的細節過分挑剔。

如果你試圖建立一個更好的算法，它會更加有用與略少操作尋找一個具有更好的複雜性類，不止一個。