算法基础

栏目: 编程工具 · 发布时间: 6年前

内容简介:算法的定义是完成一项任务的一系列步骤,就像一份食谱,第一步干什么,第二步干什么... 在计算机科学中,算法是完成一个任务的一系列步骤,对于完成一个任务,有好的算法也有坏的算法,找到一个优秀的算法可以让任务高效的完成。一个好的算法要满足两点给一个数 怎么找到它的立方根呢?我们知道无法找到随便一个数的精确立方根,所以我们可以接受一定误差。我们可以让 从0开始不断的增加它的大小,看它的三次方有多接近 ,找出最接近 的数。

算法的定义是完成一项任务的一系列步骤,就像一份食谱,第一步干什么,第二步干什么... 在计算机科学中,算法是完成一个任务的一系列步骤,对于完成一个任务,有好的算法也有坏的算法,找到一个优秀的算法可以让任务高效的完成。一个好的算法要满足两点 正确性高效 ,但是有时候也不要去完全正确足够好就行,比如一项任务要得到一个完全正确结果需要非常长的时间。

找到立方根

给一个数 怎么找到它的立方根呢?我们知道无法找到随便一个数的精确立方根,所以我们可以接受一定误差。

我们可以让 从0开始不断的增加它的大小,看它的三次方有多接近 ,找出最接近 的数。

def cuberoot(n):
    inc = 0.001 # 每次递增的数,越小精度越大
    eps = 0.01 # 可接受的误差范围
    ans = 0.0
    while abs(ans ** 3 - n) >= eps and ans < abs(n):
        ans += inc
    if n < 0: ans *= -1
    return ans
复制代码

可以猜到当 很大时,这个算法需要的时间就非常长。那么有什么更好的算法?

二分搜索算法

二分搜索算法(binary search)也叫折半搜索,是一种在有序数组中查找某一特定元素的搜索算法。从数组的中间开始寻找,看是不是要找的数,如果不是就看这个数字是大于还是小于要找的数,然后把不对的那一半扔掉。这个算法每次都搜索范围缩小一半,所以是一个非常快的算法。

算法基础

上面找到立方根问题用 二分搜索算法 解决就是这样,

def cuberoot(n):
    eps = 0.01
    low = 0.0 # 下界
    high = n # 上界
    ans = (low + high) / 2
    while abs(ans ** 3 - n) >= eps:
        if ans ** 3 < n:
            low = ans
        else:
            high = ans
        ans = (low + high) / 2
    if n < 0: ans *= -1
    return ans
复制代码

对比原来的算法可以看到,二分搜索算法快多了,原来到迭代几千次,现在十几次就行了!但是还有没有更快的算法呢?

牛顿法

牛顿法(Newton's method)又称为牛顿-拉弗森方法(Newton-Raphson method)。简单来说牛顿法可以快速的找到任何多项式的根(不光是立方根)。比如我们要找到25的平方根,首先找到一个多项式 满足 ,并对它求导得到 ,牛顿法告诉我们如果一个数 很接近它的根,那么 就更加接近它的根。

def cuberoot(n):
    eps = 0.01
    g = n / 3 # 随便猜个数
    while abs(g ** 3 - n) >= eps:
        g = g - (g ** 3 - n) / (g ** 2 * 3)
    return g
复制代码

可以看到代码很紧凑,但是非常快比二分搜索算法还要看!

大O符号

上面的方法都接近一个问题,但是有快有慢,那么我们怎么描述一个算法的快慢?

  1. 我们需要根据输入大小确定算法需要多长时间。
  2. 我们必须知道函数随输入大小增长的速度。

大O符号(Big O notation),又称为渐进符号,是用于描述函数渐近行为的数学符号。更确切地说,它是用另一个(通常更简单的)函数来描述一个函数数量级的渐近上界。在数学中,它一般用来刻画被截断的无穷级数尤其是渐近级数的剩余项;在计算机科学中,它在分析算法复杂性的方面非常有用。

大O符号描述一个算法在 最坏 情况下的复杂度。

比如有个累加函数

def add(n):
    ans = 0
    while n > 0:
        ans = ans + n
        n = n - 1
    return ans
复制代码

可以看到这个函数一共要执行 步,但是大O表示法只关心当 增大时占主导地位的项目,其他项目和系数都可以忽略。这个函数用大O符号就为 是线性复杂度。

复杂度分类(从快到慢)

符号 名称
常数
对数
多对数
线性
线性对数
多项式
指数
阶乘

加法法则

比如一个函数内有两个不同复杂度的循环,

乘法法则

比如循环嵌套循环,

其他表示符号

除了大O符号还有一些不常用的符号。

大 符号

大 符号(Big-Omega notation)的意思刚好和大O符号相反。大 符号表示函数在增长到一定程度时总大于一个特定函数的常数倍。不提供上限,算法最少要花多少时间。

大 符号

大 符号(Big-Theta notation)是大O符号和大 符号的结合。

比如一个算法上慢为 下快为 ,那么用大 表示就为 ,大 和大O看起来差不多,但是它们表达的意思不一样, 是表示随着 的增大函数实际增长率不会超过 , 是表示随着 的增大 就非常接近函数实际增长率。


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

算法设计与分析基础

算法设计与分析基础

Anany levitin / 潘彦 / 清华大学出版社 / 2007-1-1 / 49.00元

作者基于丰富的教学经验,开发了一套对算法进行分类的新方法。这套方法站在通用问题求解策略的高度,能对现有的大多数算法都能进行准确分类,从而使本书的读者能够沿着一条清晰的、一致的、连贯的思路来探索算法设计与分析这一迷人领域。本书作为第2版,相对第1版增加了新的习题,还增加了“迭代改进”一章,使得原来的分类方法更加完善。 本书十分适合作为算法设计和分析的基础教材,也适合任何有兴趣探究算法奥秘的读者......一起来看看 《算法设计与分析基础》 这本书的介绍吧!

RGB转16进制工具
RGB转16进制工具

RGB HEX 互转工具

正则表达式在线测试
正则表达式在线测试

正则表达式在线测试

HSV CMYK 转换工具
HSV CMYK 转换工具

HSV CMYK互换工具