《算法图解》NOTE 1 算法的渐近表示法以及二分法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了《算法图解》NOTE 1 算法的渐近表示法以及二分法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1253字，纯文字阅读大概需要2分钟。

内容图文

这是《算法图解》的第一篇读书笔记，内容关于表示算法复杂度的渐近表示法以及一个简单但高效的算法：二分法。

1 .渐近表示法

1.1定义

算法的运行需要时间，这就需要衡量算法运行时间即时间复杂度的方式。这个衡量方式就被成为渐近表示法（大O表示法）。
渐近表示法用于描述算法在最糟糕情况下的运行时间，同时也表示了算法运行时间随问题规模扩大而增长的幅度。

1.2如何使用渐近表示法确定时间复杂度

一般而言，算法复杂度可用一个函数进行表示。之后，仅保留函数中增长幅度最大的一项，而这一项就可用于衡量该算法的时间复杂度。

1.3时间复杂度的优先级

以下为常见的渐近表示方式及复杂度的优先级。其中，时间复杂度由上往下逐渐增加。

θ(1)：常数级
θ(log(n))：对数级
θ(n)：线性级
θ(nlog(n))：对数线性级
θ(n^2)：平方级
θ(n^3)：立方级
O(n^k)：多项式级
?(k^n)：指数级
θ(n!)：阶乘级

2.二分法

2.1定义

二分法指的是在求解问题的过程中不断地折半缩减问题规模，最终在有限时间(log2 n)内求出问题答案的算法。

2.2实例

使用二分法的案例有很多，下面演示如何用二分法近似求出sqrt(2)，精度在0.00000001

#二分法近似求出sqrt(2)，精度在0.00000001
import math

def dichotomy(target,precision):
    square_target=int(target*target)
    low=0
    high=int(square_target**2)
    result=(low+high)/2
    while len(str(result))<10:
        if result**2<=square_target:
            low=result
        else:
            high=result
        result=(low+high)/2
    return result

print(dichotomy(math.sqrt(2),8))

内容总结

以上是互联网集市为您收集整理的《算法图解》NOTE 1 算法的渐近表示法以及二分法全部内容，希望文章能够帮你解决《算法图解》NOTE 1 算法的渐近表示法以及二分法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

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

内容手机端

---