3

MIT python プログラミング コース、レクチャー 8 からのコードがあります。

def(x):
    assert type(x) == int and x >= 0
    answer = 0 
    s = str(x)
    for c in s :
        answer += int(c)
    return answer

教授が言うように、このコードの複雑さは (x) の 10 を底とする対数です。彼は、（私が理解できたように）各ループ反復では、C は 10 桁（0 ～ 9）のいずれかになり、これにより基数 10 が対数になると説明しています。

しかし、私は理解できません。なぜそうなのですか？原因の複雑さは、C の選択のバリエーションではなく、実際にはリスト S の長さに依存します。

誰か説明できますか？

4

3 に答える 3

3

さて、あなたは実際にあなたの質問にすでに答えました：

複雑さは実際にはリスト S の長さに依存し、 C の選択のバリエーションではありません

list の長さはSnumber の桁数xです。そして、数字の桁数は、その対数の下限に 1 を加えたものです。

Range of numbers   Range of log (base 10) value    Number of digits
           1 - 9                         [0, 1)                   1
         10 - 99                         [1, 2)                   2
       100 - 999                         [2, 3)                   3
     1000 - 9999                         [3, 4)                   4
   10000 - 99999                         [4, 5)                   5

したがって、数値が何であれ、ここで重要なのはその桁数だけであり、その数値は に等しくなりfloor(log10(x)) + 1ます。

これは任意の基数に一般化できます。整数nの基数表現の桁数は、基数plusの対数の下限値に等しくなります。bxbx1

たとえば、2 進数のビット数は次のようになります。

Decimal range    Binary range    Range of log (base 2) value    Number of bits
            1               1                         [0, 1)                 1
        2 - 3         10 - 11                         [1, 2)                 2
        4 - 7       100 - 111                         [2, 3)                 3
       8 - 15     1000 - 1111                         [3, 4)                 4
      16 - 31   10000 - 11111                         [4, 5)                 5
于 2013-10-11T13:44:03.953 に答える
2

彼は、（私が理解できたように）各ループ反復では、C は 10 桁（0 ～ 9）のいずれかになり、これにより基数 10 が対数になると説明しています。

それは理由ではありません。どの値を取ることができるかは問題ではありませんc。重要なのは、それが取る値の数です。答えは、 の各桁に対して 1 つの値を取るということですx。そしてx、O(log 10 x ) 10 進数を持っています。これが数値表現のしくみです。任意の基数bの任意の数値nの表現には、 log b n +1 桁があります。

于 2013-10-11T13:33:01.830 に答える