計算一個數字中的位數 - 這兩個解決方案哪一個更快？

我最近在採訪中被問到如何編寫一個算法來計算給定數字中的位數。因此，舉例來說，如果我得到了一些500的結果將是3.如果我得到了一些15345的結果將是5計算一個數字中的位數 - 這兩個解決方案哪一個更快？

我想出了2個可能的解決方案：

遞歸鴻溝數值減10，直到結果小於1，然後返回我做出的遞歸計數。
將數字轉換爲字符串，然後計算此字符串中元素的數量。

然後詢問當使用非常大的數字時哪種操作更有效，我無法給出正確的答案。所以我的問題是這裏的正確答案是什麼 - 哪種算法更快，爲什麼？

來源

2014-02-17 Marko

如何迭代地將數字除以10直到結果小於10？ –

如果這是一個非常大的數字 - 它是如何表示的？一個'int'或甚至'long'是不夠的。什麼語言？ – amit

@TedHopp是的，這是我的解決方案，但我的問題是，當我使用大數字時，我給出的兩個解決方案中的哪一個更快？ – Marko

好了，到一個整數轉換爲字符串，基本itoa（整數字符串）功能的工作原理有點像這樣：

result = "" 
while (number > 0) 
{ 
    digit = number % 10 
    append digit to result 
    number = number/10 
}

那麼，有沒有那麼多的第一和之間的差異第二個解決方案。第一種解決方案將採取O（n）迭代，其中n是整數中的位數。第二種解決方案將具有相同的複雜性，並且另外計數字符串中的Ñ位數O（n）的時間，總共O（2N） = O（n）的複雜性。

其他算法是可能的。例如，您可以查看設置的最高位，並將其與值表進行匹配。

來源

2014-02-17 19:45:06 Virtlink

問題不是關於大O符號，而是關於執行時間。常量很重要。 – amit

@amit如果沒有一個實際的實現，你可以說關於執行時間的事情毫無用處。通過對算法的總體概述，人們可以做出的唯一表述就是時間複雜度。 – Virtlink

我知道，這就是爲什麼我投票結束而不是回答無法回答的問題。我從這個問題中唯一可以看出的是它不是關於大O符號，並且提供的答案不回答問題，不管實現如何。 – amit

這很大程度上取決於如何給出數字。我會解釋你給一個數字存儲爲一個機器整數。在那種情況下，我認爲最重要的是取數字的對數，這應該在不變的時間內給出答案。

你的答案都在線性時間內運行，所以它們應該被認爲是相當於。

來源

2014-02-17 19:40:56

我不知道是什麼讓你認爲在輸入大小方面日誌不是線性的。應該閱讀，不是嗎？至於「他們應該是等同的」。常量在這樣的問題中很重要。生活並不是很大的O符號。 – amit

那麼，@amit，也是10除以不是恆定時間？ –

我計時三種變體：

重複除法
對數
串長度

爲10的倍數的長度我跑10000點每個運行。

結果以微秒：

length  division  logarithm  string length 
--------------------------------------------------- 
    10   7   10   16 
    20   14   14   26 
    30   28   14   41 
    40   46   14   59 
    50   73   14   80 
    60   91   14   80 
    70   113   14   98 
    80   136   14   106 
    90   170   14   116 
100   197   14   129

有這些數據的各種來源的文物，但我覺得你的想法。

來源

2014-02-17 21:12:01 Svante

當給出結果時，你也應該給代碼產生這些結果。就目前而言，你幾乎要求我們相信你知道你在做什麼（沒有辦法驗證你說的是什麼，沒有從頭開始編寫我們自己的程序，這可能不會產生相同的結果）。 – Dukeling

我將在今天晚些時候發佈我的代碼。但是，如果從頭開始編寫自己的程序，除非使用相同的bignum實現，相同的字符串實現和相同的對數實現，否則它絕對不會產生相同的結果。這不是一篇科學文章，只是一個快速測試。我在一個不太新近的宏碁筆記本電腦上用了一個合理的近期的SBCL。 – Svante

只是爲了記錄在案，這是做到這一點的最快方法，假設輸入是一個unsigned long或者int某種：

int count_digits(unsigned long n){ 
    unsigned long long quotient; 
    unsigned int ctDigits = 1; 
    while(n > 9){ 
     ctDigits++; 
     quotient = (n >> 1) + (n >> 2); 
     quotient += (quotient >> 4); 
     quotient += (quotient >> 8); 
     quotient += (quotient >> 16); 
     quotient = quotient >> 3; 
     n -= ((quotient << 2) + quotient) << 1; // computes the remainder 
    } 
    return ctDigits; 
}

使用部門（包括任何itoa /字符串中的任何解決方案轉換）將會慢得多，因爲分割是一項昂貴的操作。在高速計算領域，這是一件壞事，壞事。

來源

2014-02-17 22:16:20

計算一個數字中的位數 - 這兩個解決方案哪一個更快？

回答

相關問題