一文搞懂算法的时间复杂度与空间复杂度

一 时间复杂度的概念

  一般情况下,算法的基本操作重复执行的次数是模块n的某一函数f(n),因此,算法的时间复杂度记做 T(n) = O(f(n))。 随着模块n的增大,算法执行的时间增长率f(n)的增长率成正比,所以f(n)越小,算法的时间复杂度越低,算法的效率越高。   时间复杂度是总运算次数表达式中受n的变化影响最大的那一项(不含系数)   举个简单的例子:

int value = 0;                    // 执行了1次
for (int i = 0; i < n; i++) {     // 执行了n次
    value += i;
}

  这个算法执行了 1 + n 次,如果n无限大,我们可以把前边的1忽略,也就是说这个算法执行了n次。时间复杂度常用大O符号表示,这个算法的时间复杂度就是O(n)。

二 计算时间复杂度

  1. 计算出基本操作的执行次数T(n)   基本操作即算法中的每条语句(以;号作为分割),语句的执行次数也叫做语句的频度。在做算法分析时,一般默认为考虑最坏的情况。
  2. 计算出T(n)的数量级   求T(n)的数量级,只要将T(n)进行如下一些操作: 忽略常量、低次幂和最高次幂的系数,令f(n)=T(n)的数量级。
  3. 用大O来表示时间复杂度   当n趋近于无穷大时,如果lim(T(n)/f(n))的值为不等于0的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))。   只保留最高阶项,最高阶项存在且不是1,则去除与这个项相乘的常数。

用一个例子来表明以上的步骤:

for(i=1;i<=n;++i)
  {
     for(j=1;j<=n;++j)
     {
         c[ i ][ j ]=0; //该步骤属于基本操作 执行次数:n^2
          for(k=1;k<=n;++k)
               c[ i ][ j ]+=a[ i ][ k ]*b[ k ][ j ]; //该步骤属于基本操作 执行次数:n^3
     }
  } 

第一步计算基本语句执行次数:T(n)= n^2+n^3; 第二步T(n)的同数量级,我们可以确定 n^3为T(n)的同数量级; 第三步用大O表示时间复杂度:T(n)=O(n^3)。

三 常见的时间复杂度

执行次数函数

名称

3

O(1)

常数阶

2n+3

O(n)

线性阶

3n2+2n+1

O(n2)

平方阶

5log2n+2

O(log2n)

对数阶

2n+3nlog2n+1

O(nlogn)

nlog2n阶

6n3+2n2+3n+4

O(n3)

立方阶

2n

O(2n)

指数阶

最常见的多项式时间算法复杂度关系为:

O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3)

指数时间算法复杂度关系为:

O(2n) < O(n!)< O(nn)

举个例子来说明上述的时间复杂度:

i=1;       // 执行次数:1
while (i<=n)
   i=i*2;  
   // 频度为f(n),2^f(n)<=n;f(n)<=log2n
   // 每次i*2后,距离结束循环更近了。也就是说有多少个2相乘后大于n。
   // 取最大值f(n)=log2n,T(n)=O(log2n )

四 复杂情况的时间复杂度分析

1.并列循环复杂度分析

for (i=1; i<=n; i++)
  for (j=1; j<=n; j++)
          x++;     //O(n2)

2.函数调用的复杂度分析

public void printsum(int count){
    int sum = 1;
    for(int i= 0; i<n; i++){
       sum += i;
    }   
    System.out.print(sum);
}

  记住,只有可运行的语句才会增加时间复杂度,因此,上面方法里的内容除了循环之外,其余的可运行语句的复杂度都是O(1)。   所以printsum的时间复杂度 = for的O(n)+O(1) = 忽略常量 = O(n)

五 空间复杂度

  空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度,记做S(n)=O(f(n))。   比如直接插入排序的时间复杂度是O(n^2),空间复杂度是O(1) 。而一般的递归算法就要有O(n)的空间复杂度了,因为每次递归都要存储返回信息。   例如关于O(1)的问题, O(1)是说数据规模和临时变量数目无关,并不是说仅仅定义一个临时变量。举例:无论数据规模多大,我都定义100个变量,这就叫做数据规模和临时变量数目无关。就是说空间复杂度是O(1)。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏iOSDevLog

数据结构和算法

数据结构和算法是计算机科学中最重要的概念之一。如果您不熟悉计算机科学或编程,本文将为您提供有关数据结构和算法的概述。这也是Landscape系列的第二集。

1094
来自专栏架构之路

寻找第K元素的八大算法、源码及拓展

一、问题描述  所谓“第(前)k大数问题”指的是在长度为n(n>=k)的乱序数组中S找出从大到小顺序的第(前)k个数的问题。 第K大问题可以是现实问题,譬如竞价...

3256
来自专栏Leetcode名企之路

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

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

602
来自专栏文武兼修ing——机器学习与IC设计

表的应用——排序与描述多项式排序多项式ADTGO语言笔记

排序 朴素排序 在链表建立的过程中可以直接完成排序功能,即建立一个新链表并将源数据一个一个存进新链表中,每个元素存储的位置在小于这个元素的节点和大于这个元素的节...

3306
来自专栏小筱月

各种排序算法

冒泡排序还有一种优化算法,就是立一个flag,当在一趟序列遍历中元素没有发生交换,则证明该序列已经有序

853
来自专栏青青天空树

小白详细讲解快速幂--杭电oj2035-A^B

输入数据包含多个测试实例,每个实例占一行,由两个正整数A和B组成(1<=A,B<=10000),如果A=0, B=0,则表示输入数据的结束,不做处理。

943
来自专栏开发与安全

从零开始学C++之STL(四):算法简介、7种算法分类

一、算法 算法是以函数模板的形式实现的。常用的算法涉及到比较、交换、查找、搜索、复制、修改、移除、反转、排序、合并等等。 算法并非容器类型的成员函数,而是一...

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

浅谈积性函数的线性筛法

假设$n = p_1^{a_1} p_2^{a_2} \dots p_k^{a_k}$

952
来自专栏Dawnzhang的开发者手册

数据结构与算法学习笔记之 从0编号的数组

数组看似简单,但掌握精髓的却没有多少;他既是编程语言中的数据类型,又是最基础的数据结构;

983
来自专栏aCloudDeveloper

漫谈递归转非递归

一:递归的思想       之前面试腾讯,面试官问了一个问题:说说递归和循环的区别?当时没有答出问题的本质,只是简单地解释了这两个词的意思,囧,今天就借由这篇文...

2177

扫码关注云+社区