日誌功能的複雜性是什麼？

log base 10函數的複雜程度是多少？日誌功能的複雜性是什麼？

來源

2011-09-06 Paul Manta

這功課嗎？ –

這不會取決於所使用的算法嗎？查找表例如是O（1）。 – Thilo

@Tony：[No]（http://math.stackexchange.com/questions/61759/project-euler-problem-25） –

這真的取決於你想要計算什麼值的域的對數。

對於IEEE雙打，許多處理器可以在單個彙編指令中取對數;例如，x86具有FYL2X和FYL2XP1指令。雖然通常這樣的指令將只需要對數在一些固定的基礎上，它們可以被用於通過使用這樣的事實採取任意的鹼基對數的是

日誌_一個 B =登錄_Ç B /登錄_c a

通過簡單地取兩個對數並找到它們的商。

對於一般整數（任意精度），可以使用重複平方與二分搜索相結合，僅使用O（log log n）算術運算取對數（每次對一個數字進行平方運算時，指數加倍，即您只能將數字記錄日誌平方n次，然後才能超過其值並可執行二分查找）。使用some cute tricks with Fibonacci numbers，您只能在O（log n）空間中執行此操作。如果你正在計算binary logarithm，你可以使用一些可以使用位移的可愛技巧來在更短的時間內計算值（儘管漸近複雜度是相同的）。

對於任意實數，邏輯更難。儘管我承認我不熟悉這樣做的方法，但可以使用牛頓法或泰勒級數來計算一定精度的對數。然而，你很少需要這樣做，因爲大多數實數都是IEEE雙精度值，在這種情況下有更好的算法（甚至硬件指令）。

希望這會有所幫助！

來源

2011-09-06 09:17:08 templatetypedef

對於整數，通常還有一個指令（或一個短序列）來執行'CTZ（x ＆（x - 1））'或'wordsize - LZC（x）'） - 但AFAIK對時間複雜度根本沒有幫助（只是實際速度） – harold

@ harold-雖然只適用於二進制對數。 – templatetypedef

@templatetypedef你可以乘以一個常數因子來獲得任何其他基數的對數，就像你剛剛演示的那樣。 :) –

日誌功能的複雜性是什麼？

回答

相關問題