数据结构(二)之算法基础

  一.为什么要学习算法?

    先来个简单的算法比较:求sum=1+2+3+...+(n-1)+n的结果. 输入整数n,输出 sum        解法一:for循环

  function sum(n){
        var s=0;            //执行1次
        for(var i=1;i<n+1;i++){   
            s+=i;           //执行n+1次

     } 

      解法二:

function sum(n){
     return n*(n-1)/2;    //执行1次
 }

    很明显,解法二要优于解法一。因为解法二需要运算的次数少。我们去衡量一个算法的好坏主要是从时间复杂度和空间复杂度来看的,其次才到可读性,可维护性。那么接下来讲讲怎么来计算时间复杂度与空间复杂度。

  二.时间复杂度的计算:

    推导大O阶来计时间复杂度

    规则:1.用常数1取代运行时间中的所有加法常数(即常数阶都计为O(1) );

       2.在修改后的运行次数函数中,只保留最高阶项;

       3.如果最高阶项存在且不是1,则去除与这个项相乘的常数

     解法一的运行次数:  f1(n) = 1+n+1+1=n+3 次  时间复杂度记作 T(n) = O( f1(n) )  //n+3直接舍掉常数,变为n ,名为“线性阶”

     解法二的运行次数: f2(n) = 1次        时间复杂度记作 T(n) = O( f1(1) )  //名为“常数阶”

     由此可知解法一随n的增加,运行次数也增加,而解法二始终只需运行一次

    对数阶:

function count(n){
    var c=1;      //执行1次
    while(c<n){
        c=c*2;  //执行log2n次
    也就是说2的多少次冪大于n,就运行了多少次。时间复杂度计做O(logn),名为对数阶。
    平方阶:
function num(n){
    var count=0;
    for(var i=0;i<n;i++){  //执行 n 次
        for(var j=i;j<n;j++){
            count++;        //执行 n-i 次
        }
    }
    return count;
}
   以上代码执行总次数为n+(n-1)+(n-2)+...+1 = n2/2+n/2 次,用大O推导法去掉相加常数n/2,去掉相乘常数1/2,所以时间复杂度为O(n2)
   总结:
    时间复杂度有多种,这里是讨论常见的阶。常用的时间复杂杂耗时的时间从小到大依次为:
    O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n) < O(n!) <O(nn)

   扩展:最坏时间复杂度

    例:给出一个数组arr,里面有n个随机数,找出arr中的指定数字。那么这个数字有可能出现在数组中的第一个位置,时间复杂度为O(1);也可能出现在数组最后一个位置,时间复杂度为O(n) ,从概率来说,平均查找时间应该是n/2次。

    最坏时间复杂度从字面上就能理解,时间最长的情况,时间不会更长,情况不会更坏了。通常没有特殊说明,我们计算的时间复杂度都为最坏时间复杂度。    

  三.算法空间复杂度

    算法的空间复杂度并不是计算实际占用的空间,而是计算整个算法的辅助空间单元的个数,与问题的规模没有关系。算法的空间复杂度S(n)定义为该算法所耗费空间的数量级。S(n)=O(f(n)) 若算法执行时所需要的辅助空间相对于输入数据量n而言是一个常数,则称这个算法的辅助空间为O(1)。通常,我们用时间复杂度来衡量算法的优略。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏fangyangcoder

leetcode(三)

给定一个二维的矩阵(矩阵的数全由1和0组成),任意反转矩阵的每一行和每一列(0反转成1,1反转成0),求出最大矩阵分数,矩阵分数的求法是矩阵每一行代表二进制数,...

853
来自专栏数值分析与有限元编程

坐标映射

建立等参单元,需要另外一个自然坐标系下的参考单元。对于物理坐标系下的任意一点,在自然坐标系下的参考单元中,有唯一的一个点与之对应;反过来对于自然坐标系下参考单元...

2684
来自专栏Kiba518

单源最短路径解析

1,设0为源点,建立两个集合S,T,S保存节点0,T集合保存节点1,2,3,4。(S,T是官方定义名称,个人理解S应该是source的缩写,T是target的缩...

752
来自专栏Python中文社区

NumPy二元运算的broadcasting机制

NumPy中有一个非常方便的特性:broadcasting。当我们对两个不同长度的numpy数组作二元计算(如相加,相乘)的时候,broadcasting就在背...

3328
来自专栏wym

opencv学习笔记--四则运算

参考博客:https://blog.csdn.net/u011321546/article/details/79557092

742
来自专栏计算机视觉与深度学习基础

全排列生成算法:next_permutation

概念 全排列的生成算法有很多种,有递归遍例,也有循环移位法等等。C++/STL中定义的next_permutation和prev_permutation函数则...

1916
来自专栏xingoo, 一个梦想做发明家的程序员

cuda中的二分查找

  使用背景 通常,在做高性能计算时,我们需要随机的连接某些点。这些点都具有自己的度量值,显然,度量值越大的值随机到的概率就会越大。因此,采用加权值得方法: v...

1765
来自专栏C/C++基础

Dijkstra算法求单源最短路径

在一个连通图中,从一个顶点到另一个顶点间可能存在多条路径,而每条路径的边数并不一定相同。如果是一个带权图,那么路径长度为路径上各边的权值的总和。两个顶点间路径长...

601
来自专栏mathor

科学计算库Numpy

 genfromtxt函数里穿了三个参数,分别是 要打开的文档名称,分隔符,以什么类型存储  打印结果:

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

数学笔记(一)之列主序矩阵

对于矩阵,OpenGL采用列主序(column-major order)存储,之前对于这个概念有些模糊,后来又了解了一些相关知识,在此一记~

951

扫码关注云+社区