时间复杂度是最好的还是最坏的 终于把时间复杂度和空间复杂度

俗话说,“语言只是工具,算法才是程序的灵魂”对于程序员来说,算法始终是一个绕不开的门槛近两年,越来越多的互联网公司在招聘环节注重算法的考察,下面我们就来聊聊关于时间复杂度是最好的还是最坏的 终于把时间复杂度和空间复杂度?接下来我们就一起去了解一下吧!

时间复杂度是最好的还是最坏的 终于把时间复杂度和空间复杂度

时间复杂度是最好的还是最坏的 终于把时间复杂度和空间复杂度

前言

俗话说,“语言只是工具,算法才是程序的灵魂”。对于程序员来说,算法始终是一个绕不开的门槛。近两年,越来越多的互联网公司在招聘环节注重算法的考察。

什么是好的算法?

我们通常有下面两个指标:

  • 空间复杂度:根据算法写成的程序在执行时占用存储单元的长度。
  • 时间复杂度:根据算法写成的程序在执行时耗费时间的长度。

在实践中或面试中,我们不仅要能够写出具体的算法来,还要了解算法的时间复杂度和空间复杂度,这样才能够评估出算法的优劣。当时间复杂度和空间复杂度无法同时满足时,还需要从中选取一个平衡点。

如何计算时间复杂度?

常见的时间复杂度量级有:

  • 常数阶O(1)
  • 对数阶O(logN)
  • 线性阶O(n)
  • 线性对数阶O(nlogN)
  • 平方阶O(n²)
  • 立方阶O(n³)
  • 指数阶(2^n、n!、n^n)

上面从上至下依次的时间复杂度越来越大,执行的效率越来越低。优劣排序如下:O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3)< O(2^n) < O(n!) < O(n^n)

求解算法复杂度一般分以下几个步骤:

  • 找出算法中的基本语句:算法中执行次数最多的语句就是基本语句,通常是最内层循环的循环体。
  • 计算基本语句的执行次数的数量级:只需计算基本语句执行次数的数量级,即只要保证函数中的最高次幂正确即可,可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析,使注意力集中在最重要的一点上:增长率。
  • 用大Ο表示算法的时间性能:将基本语句执行次数的数量级放入大Ο记号中。

其中用大O表示法通常有三种规则:

  • 用常数1取代运行时间中的所有加法常数;
  • 只保留时间函数中的最高阶项;
  • 如果最高阶项存在,则省去最高阶项前面的系数;

下面通过具体的实例来说明以上的推算步骤和规则:

(1) 常数阶O(1)

无论代码执行了多少行,只要是没有循环等复杂结构,那这个代码的时间复杂度就都是O(1),如:

int i = 1; int j = 2; i; j ; int k = i j;

上述代码执行时,单个语句的频度均为1,不会随着问题规模n的变化而变化。因此,算法时间复杂度为常数阶,记作T(n)=O(1)。这里我们需要注意的是,即便上述代码有成千上万行,只要执行算法的时间不会随着问题规模n的增长而增长,那么执行时间只不过是一个比较大的常数而已。此类算法的时间复杂度均为O(1)。

(2)对数阶O(log n)

int i = 1; // ① while (i <= n) { i = i * 2; // ② }

在上述代码中,语句①的频度为1,可以忽略不计。

语句②我们可以看到它是以2的倍数来逼近n,每次都乘以2。如果用公式表示就是1*2*2*2…*2 <=n,也就是说2的x次方小于等于n时会执行循环体,记作2^x <= n,于是得出x<=logn。也就是说上述循环在执行logn次之后,便结束了,因此上述代码的时间复杂度为O(log n)。

其实上面代码的时间复杂度公式如果精确的来讲应该是:T(n) = 1 O(log n),但我们上面已经讲到对应的原则,“只保留时间函数中的最高阶项”,因此记作O(log n)。

(3)线性阶O(n)

int j = 0; // ① for (int i = 0; i < n; i ) { // ② j = i; // ③ j ; // ④ }

上述代码中,语句①的频度为1,②的频度为n,③的频度为n-1,④的频度为n-1,因此整个算法可以用公式T(n)=1 n (n-1) (n-1)来表示。进而可以推到T(n)=1 n (n-1) (n-1)=3n-1,即O(n)=3n-1,去掉低次幂和系数即O(n)=n,因此T(n)=O(n)。

在上述代码中for循环中的代码会执行n遍,因此它消耗的时间是随着n的变化而成线性变化的,因此这类算法都可以用O(n)来表示时间复杂度。

(4)线性对数阶O(nlogN)

for (int m = 1; m < n; m ) { int i = 1; // ① while (i <= n) { i = i * 2; // ② } }

线性对数阶要对照对数阶 O(log n)来进行理解。上述代码中for循环内部的代码便是上面讲到对数阶,只不过在对数阶的外面套了一个n次的循环,当然,它的时间复杂度就是n*O(log n)了,于是记作O(nlog n)。

(5)平方阶O(n²)

int k = 0; for (int i = 0; i < n; i ) { for (int j = 0; j < n; j ) { k ; } }

平方阶可对照线性阶来进行理解,我们知道线性阶是一层for循环,记作O(n),此时等于又嵌套了一层for循环,那么便是n * O(n),也就是O(n * n),即O(n^2)。

(6)立方阶O(n³)

int a = 0; for (int i = 0; i < n; i ) { for (int j = 0; j < n; j ) { for (int k = 0; k < n; k ) { a ; } } }

同理,立方阶O(n³)相对于平方阶O(n²),只不过是多嵌套了1层循环而已。那么便是n * O(n*n),也就是O(n * n * n),即O(n^3)。

(6)指数阶O(2^n)

int Fibonacci(int number) { if (number <= 1) return number; return Fibonacci(number - 2) Fibonacci(number - 1); }

O(2^n),表示一个算法的性能会随着输入数据的每次增加而增大两倍,典型的方法就是上述代码中裴波那契数列的递归计算的实现。

严格来说,斐波那契数列的时间复杂度的紧界不是 O(2^n),而是O(((1 √5)/ 2)^n),有兴趣的同学可以自己推导一下~

如何计算空间复杂度?

程序执行除了需要存储空间、指令、常数、变量和输入数据外,还包括对数据进行操作的工作单元和存储计算所需信息的辅助空间。存储空间通常包括:指令空间(即代码空间)、数据空间(常量、简单变量)等所占的固定部分和动态分配、递归栈所需的可变空间。其中可变空间与算法有关。

一个算法所需的存储空间用f(n)表示。S(n)=O(f(n))其中n为问题的规模,S(n)表示空间复杂度。

下面看两个常见的空间复杂度示例:空间复杂度O(1)和O(n):

(1)空间复杂度 O(1)

int i = 1; int j = 2; int k = i j;

上述代码中临时空间并不会随着n的变化而变化,因此空间复杂度为O(1)。

总结一下就是:如果算法执行所需要的临时空间不随着某个变量n的大小而变化,此算法空间复杂度为一个常量,可表示为 O(1),即 S(n) = O(1)。

(2)空间复杂度 O(n)

int j = 0; int[] m = new int[n]; for (int i = 1; i <= n; i) { j = i; j ; }

上述代码中,只有创建int数组分配空间时与n的大小有关,而for循环内没有再分配新的空间,因此,对应的空间复杂度为S(n) = O(n)。

,

免责声明:本文仅代表文章作者的个人观点,与本站无关。其原创性、真实性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容文字的真实性、完整性和原创性本站不作任何保证或承诺,请读者仅作参考,并自行核实相关内容。文章投诉邮箱:anhduc.ph@yahoo.com

    分享
    投诉
    首页