恆定輸入的漸近表示

Question

如果我有一個算法，其中輸入只是一個數字，輸出是它的除數集合。所以我的輸入總是一個數字，算法中的迭代次數取決於如何這個數字很大。這樣一個算法的大喔？ 算法：

1: Set m := 2. 
2: Set S := {} for S a multi-set. 
3: while m <= n^0.5 
do 
4: if m divides N then 
5: Set S U m 
6: else 
7: Set m = m + 1. 
8: end if 
9: end while 
10: Return the set S of divisors found. 

Answer 1

您可以讓大O符號變量的漸近複雜性是輸入數字本身，或者也可以是數來表達需要數位的。這兩個約定引起了不同的漸近分類，所以清楚說明在報告結果時使用哪一個是很重要的。

一般來說，當人們談論數字太大以至於需要數字的情況時，人們傾向於使用數字位數約定，而當輸入被數字限制時，數字含義數字約定機器字的大小。但除此之外，這不是您可以依賴的第一個猜測，您需要驗證自己是否適合您的特定情況。

該選擇傾向於與您用於算術運算的成本模型攜手共存。當你計算位數時，通常假設n位值的運算花費O（n）時間，而當你處理輸入數字的含義時，通常假定數字運算的運算時間是固定的。在你的情況下，你會得到類似O（2^n）或O（sqrt（m））的東西，其中n是輸入中的位數，m是輸入本身。 （細節取決於您的multiset基元如何執行）。請參閱pseudo-polynomial time。