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

  一.为什么要学习算法?

    先来个简单的算法比较:求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 条评论
登录 后参与评论

相关文章

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

OpenGL ES Shading Language 2.0 参考笔记

声明 struct matStruct { vec4 ambientColor; vec4 diffuseColor; ...

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

全排列生成算法:next_permutation

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

2016
来自专栏desperate633

LintCode 搜索旋转排序数组题目分析代码

假设有一个排序的按未知的旋转轴旋转的数组(比如,0 1 2 4 5 6 7 可能成为4 5 6 7 0 1 2)。给定一个目标值进行搜索,如果在数组中找到目标值...

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

编程小知识之 Random接口返回值

平日工作中,(伪)随机数的使用一定是避不开的,拿 C# 为例,System 命名空间下的 Random 类型一般都是我们生成(伪)随机数的第一选择:

793
来自专栏前端儿

三角形面积

输入每行是一组测试数据,有6个整数x1,y1,x2,y2,x3,y3分别表示三个点的横纵坐标。(坐标值都在0到10000之间) 输入0 0 0 0 0 0表示输...

1142
来自专栏数据结构与算法

P3391 【模板】文艺平衡树(Splay)

题目背景 这是一道经典的Splay模板题——文艺平衡树。 题目描述 您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:翻转一个区...

3997
来自专栏Python攻城狮

科学计算工具Numpy1.ndarray的创建与数据类型2.ndarray的矩阵运算ndarray的索引与切片3.ndarray的元素处理元素判断函数元素去重排序函数4.2016年美国总统大选民意调查

Numpy:提供了一个在Python中做科学计算的基础库,重在数值计算,主要用于多维数组(矩阵)处理的库。用来存储和处理大型矩阵,比Python自身的嵌套列表结...

1173
来自专栏前端吧啦吧啦

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

3797
来自专栏Python小屋

Python高级数组处理模块numpy用法精要

numpy是Python的高级数组处理扩展库,提供了Python中没有的数组对象,支持N维数组运算、处理大型矩阵、成熟的广播函数库、矢量运算、线性代数、傅里叶变...

3077
来自专栏程序生活

连续子数组的最大和

题目1 连续子数组的最大和 描述: 输入一个整型数组,数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度...

2845

扫码关注云+社区