美文网首页
算法:基本概念

算法:基本概念

作者: 沙漠中的猴 | 来源:发表于2018-11-16 18:02 被阅读0次

    什么是算法?

    算法解决某个特定问题步骤的描述。

    算法的特性

    1. 输入:可以是零个或者多个输入。
    2. 输出:可以是一个或者多个输出。
    3. 有穷性:无限循环肯定是不可以的。
    4. 确定性:相同的输入,一定要得到相同的输出。
    5. 可行性:每一步都必须在有限次数内完成。

    算法的设计要求

    1. 正确性:可以正确的解决问题
    2. 可读性:方便阅读、理解和交流
    3. 健壮性:输入不合法会做出相应的处理。
    4. 效率高且存储量低。

    算法效率的度量方法

    算法的效率一般是指执行的时间。

    事后统计法

    对比多种算法的执行时间。

    事前估算法

    假如我们要求解1+2+3+···+100的和:

    算法1:

        sum,n := 0,100              // 执行1次
        for i:=1; i<=n; i++ {       // 执行 n+1 次
            sum +=i                // 执行 n 次
        }
    

    算法2:

    sum, n := 0,100          // 执行 1 次
    sum = n*(n+1)/2        // 执行 1 次
    

    很显然算法一执行了2n+2次,算法二执行了2 次。忽略掉算法的第一行指令,也就是n次与1次的差别。

    假设有一个算法3是下面的内容:

    sum,n,m := 0,100,200
        for i := 0; i < n; i++ {
            for j := 0; j < n; j++ {
                sum ++                // 执行了 n * n 次
            }
        }
    

    我们通常在估算算法的效率时通常会忽略常数项,只是比较最高次幂。

    比如说:算法A是 2n*n ,算法B是 3n+1,算法C 是 2n*n+3n+1。那么算法A的时间复杂度是O(n*n),算法B的时间复杂度是O(n),算法C的时间复杂度是O( n * n )

    算法的时间复杂度

    我们通常用O来表示算法的时间复杂度。
    O(1) 通常称为:常数阶
    O(n)通常称为:线性阶
    O(n*n)通常称为:平方阶

    我们通过例子来学习推导:

    常数阶

    sum, n := 0,100          // 执行 1 次
    sum = n*(n+1)/2        // 执行 1 次
    

    上面的代码执行了2次,但是我们通常会忽略常数项,把这段代码的时间复杂度计为O(1)。也就是我们说的常数阶,哪怕这段代码执行了10次,也是计为O(1)

    线性阶

      sum,n := 0,100              // 执行1次
        for i:=1; i<=n; i++ {       // 执行 n+1 次
            sum +=i                // 执行 n 次
        }
    

    在计算时间复杂度的时候,我们通常是忽略掉常数,并将最高次幂的常数项设为1,所以上述代码的时间复杂度为:O(n)。通常称为常数阶。

    对数阶

       count, n :=1, 100
    
        for {
            if count > n {
                break
            }
    
            count = count * 2
        }
    

    由于每次count乘以 2 之后就距离 n 更近一步了。2^x = n 所以 x = logn时间复杂度也就是为O(logn)

    平方阶

    sum,n,m := 0,100,200
        for i := 0; i < n; i++ {
            for j := 0; j < n; j++ {
                sum ++                // 执行了 n * n 次
            }
        }
    
    

    这段代码的时间复杂度为: O(n^2)

    循环的时间复杂度等于循环体的复杂度乘以循环的次数。

    时间复杂度消耗时间的顺序:

    O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

    相关文章

      网友评论

          本文标题:算法:基本概念

          本文链接:https://www.haomeiwen.com/subject/tdyeoftx.html