Mod 20的大O

Question

這段代碼的大O是什麼？

def mod20(n): 
    return n%20 

它是對數線性的嗎？

你能向我描述一個大O的例子嗎？

Answer 1

假設您可以插入整數任何大小，複雜度將與劃分的複雜度相同。

所以它是O(log n)歸因於log n是位數。

注意1：如果只能插入32位或64位整數，則「複雜度」將爲O(1)。

注意2：由於電腦保存所有數字的二進制，你可以得到n % 2^k在konstant時間，即使n可以是任意大小的。你只需要k小數位。這不工作的n % 20沒有計算n代表的基地20.

如果你想知道什麼大O意味着，這post會幫助你。