Python MIT讲座：log(n)示例的复杂性

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了Python MIT讲座：log(n)示例的复杂性，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1551字，纯文字阅读大概需要3分钟。

内容图文

有麻省理工学院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可以是十位数之一(0-9),这将基数10带到logarythm.

但是我无法理解,为什么会这样呢？原因复杂性实际上取决于列表S的长度,而不是C的选择变化.

有人可以解释一下吗？

解决方法:

那么,你实际上已经回答了你的问题：

complexity actually depends of the length of list S , rather than variations of choice for C

列表S的长度是数字x中的位数.并且数字中的位数是其日志的楼层加一.

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.

这可以推广到任何数字基数：整数x的b基表示中的数字数n等于x加1的b基日志的最低值.

例如,二进制数中的位数将是

Decimal range    Binary range    Range of log (base 2) value    Number of bits
            1               1                         [0, 0]                 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

内容总结

以上是互联网集市为您收集整理的Python MIT讲座：log(n)示例的复杂性全部内容，希望文章能够帮你解决Python MIT讲座：log(n)示例的复杂性所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端