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

  一.为什么要学习算法?

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

相关文章

来自专栏Leetcode名企之路

【Leetcode】81. 搜索旋转排序数组 II

( 例如,数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。

1312
来自专栏desperate633

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

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

992
来自专栏Python小屋

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

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

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

全排列生成算法:next_permutation

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

2086
来自专栏程序生活

连续子数组的最大和

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

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

C++11新特性——range for

很多编程语言都有range for语法功能,自C++11起,终于将这个重要功能加入C++标准中。range for语句,可以方便的遍历给定序列中的每个元素并对其...

942
来自专栏kalifaの日々

线段树 BIT 求冒泡排序的交换次数

线段树特别适合与区间相关的运算,比如MRQ(minimum range query)求一段区间内的最小值。 BIT可以看作是压缩了的线段树,由于(某类)线段树...

3978
来自专栏菜鸟程序员

【Java】随机数详解

1464
来自专栏算法channel

Leetcode|Find K Closest Elements

01 — 题目 Given a sorted array, two integers k and x, find the k closest elements ...

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

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

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

883

扫码关注云+社区