《算法图解》NOTE 1-算法的渐近表示法以及二分法1 .渐近表示法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))

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏算法channel

机器学习|聚类算法之DBSCAN

DBSCAN,全称:Density-Based Spatial Clustering of Applications with Noise,是一个比较有代表性的...

4399
来自专栏xiaoxi666的专栏

矩阵求逆的几种方法总结(C++)

文内程序旨在实现求逆运算核心思想,某些异常检测的功能就未实现(如矩阵维数检测、矩阵奇异等)。

2341
来自专栏机器学习原理

NLP(3)——seq to seq

普通作弊的基础上,回顾上一刻的答案 4.学渣作弊(attention机制)

1772
来自专栏AI科技大本营的专栏

如何快速优化机器学习的模型参数

【导读】一般来说机器学习模型的优化没什么捷径可循。用什么架构,选择什么优化算法和参数既取决于我们对数据集的理解,也要不断地试错和修正。所以快速构建和测试模型的能...

1152
来自专栏tkokof 的技术,小趣及杂念

对于"矩阵连乘问题"的一点想法

在算法设计的学习中,每到“动态规划”一节,一般都会涉及到“矩阵连乘”问题(例如《Algorithms》,中文译名《算法概论》),可想而知该题的经典程度 :)

1153
来自专栏量化投资与机器学习

七步理解深度学习

原文链接请点击阅读原文。 There are many deep learning resources freely available online,but...

2049
来自专栏yw的数据分析

ONCOCNV软件思路分析之tumor处理

前期处理 perl脚本统计RC(RC(read counts)) 读入control baseline 和 sigma(最后baseline 预测的mad值) ...

40817
来自专栏ml

调参过程中的参数 学习率,权重衰减,冲量(learning_rate , weight_decay , momentum)

无论是深度学习还是机器学习,大多情况下训练中都会遇到这几个参数,今天依据我自己的理解具体的总结一下,可能会存在错误,还请指正. learning_rate , ...

8558
来自专栏小樱的经验随笔

DFS中的奇偶剪枝学习笔记

奇偶剪枝学习笔记 描述 现假设起点为(sx,sy),终点为(ex,ey),给定t步恰好走到终点, s | ...

2674
来自专栏机器之心

教程 | 如何利用散点图矩阵进行数据可视化

2158

扫码关注云+社区

领取腾讯云代金券