將小數轉換爲另一個基的時間複雜度

以下是計算小數的基本版本的代碼。我不確定它的時間複雜性。謝謝，將小數轉換爲另一個基的時間複雜度

public static String convertToBase(int num, int base) { 
    if (base > 36) { 
     throw new IllegalArgumentException("The input argument should be less than or equal to 36."); 
    } 
    final StringBuilder sb = new StringBuilder(); 
    while (num > 0) { 
     final int div = num % base; 
     if (div > 9) { 
      final int sum = div + 55; 
      sb.append((char) sum); 
     } else { 
      sb.append(div); 
     } 
     num = num/base; 
    } 
    return sb.reverse().toString(); 
}

來源

2013-07-15 JavaDeveloper

O（n）是時間複雜度在這裏 –

是吧'NUM日誌base'？ – NINCOMPOOP

我同意新白癡的智能答案。謝謝 – JavaDeveloper

算法的複雜度是

如果base = 36，NUM = 35 .............迭代次數爲1 如果base = 02 ，num = 35 ............迭代次數爲6

這裏number Iterations是= log（base）= log的基數。

因此時間複雜度爲大O（日誌（n））的

來源

2013-07-15 08:18:25

這個詞是'算法'，謝謝，不是'算法'。以一位傑出的數學家命名。 – EJP

嚴格來說，答案是O(1)。

如果int是支持任意精度的整數類型，那麼顯然答案將是O(logN)。

但它不是！一個int可以得到不大於Integer.MAX_INT與2^31-1 ...或大約20億。

因此，如果我們讓N（無界整數）傾向於無窮大，則值num將環繞，以便它永遠不會超過Integer.MAX_INT。這意味着，如果（例如）base是10，所述while迴路可以至多log10(2^31)次執行（即10次）...並convertToBase是O(1)。

不過，如果你準備濫用的術語/符號，你可以說，這是爲O(logN)足夠小N。

來源

2013-07-15 08:39:05

我真的不能買這個，對不起。任何值的時間複雜度都是O（log（N））。如果N是1，則比N是32767快。 – EJP

@EJP - 大O複雜度的定義是根據N趨於無窮的限制來定義的。這裏，num的值不能趨於無窮大。 big-O的定義並不是關於更快的定義。這是關於事情成長的速度。 –

嚴格地說，您需要先定義一個計算模型，然後才能回答問題。你顯然選擇了有限內存的計算模型。根本沒有幫助，因爲有限內存=有限輸入=有限步驟終止（如果它終止）= *每個*計算終止於恆定時間（或根本不終止）。這就是巡迴遊戲機具有無限存儲器的原因，以及爲何時間複雜度通常基於具有無限存儲器的模型。 –

正如Stephen C所說，複雜性是O（1），因爲n是有界的。（n）是乘法的複雜性（因爲存在「num/base」操作）。如果n是任意的精確數字，則複雜度將是O（M（n）log（n））。

見 http://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations#Arithmetic_functions

來源

2013-12-17 13:42:10 Dudz1978