算法基础概念

Posted by Jfson on 2017-12-12

算法的复杂度

  • 算法的复杂度: 算法的时间复杂度和空间复杂度合称为算法的复杂度,一般不特别说明,讨论的时间复杂度均是最坏情况下的时间复杂度。
  • 用于描述时间复杂度&空间复杂度的公式关键字 Big-O
  • 时间复杂度:执行程序所需的时间。可以估算出程序对处理器的使用程度。一般用内层代码语句执行次数来统计
  • 空间复杂度:执行程序所需的存储空间。可以估算出程序对计算机内存的使用程度,就是在运行过程中临时占用存储空间的大小。

Big O

image

  • 所有的复杂度:O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(n³)<O(2ⁿ)<O(n!)

  • 1、不变复杂性

1
2
3
4
5
6
O(1):称为不变复杂性
1项:1秒
10项:1秒
100个项目:1秒
项目的数量仍然增加10倍,但O(1)的比例因子总是1。
  • 2、对数复杂度
1
2
3
4
5
6
7
8
O(log n):称为对数复杂度
1项:1秒
10项:2秒
100项:3秒
1000项:4秒
10000项:5秒
计算次数只会增加输入值的对数。因此,在这种情况下,假定每个计算需要1秒钟,输入的日志n就是所需的时间log n。
  • 3、线性复杂度
1
2
3
4
5
6
O(n):称为线性复杂度
1项:1秒
10项:10秒
100个项目:100秒
这次项目数量增加了10倍,时间也增加了10倍。n = 10,所以O(n)的比例因子是10。
  • 4、二次型复杂度

    1
    2
    3
    4
    5
    6
    O(n 2):称为二次型复杂度
    1项:1秒
    10个项目:100秒
    100个项目:10000秒
    注意物品的数量增加了10倍,但时间增加了10 2倍。基本上,n = 10,所以O(n 2)给出我们的比例因子n 2,它是10 2。
  • 5.还有立方阶,阶乘等等…

    详细解释

  • 1.时间频度: 一个算法执行所耗费的时间,理论是不能算出来的,通常时间复杂度均是++最坏++情况下的时间复杂度。这时候只需要去关注++内层代码语句++的执行次数,或者哪个算法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数叫时间频度。记为T(n)。

  • 2.时间复杂度:
    算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,当n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n))为算法的渐进时间复杂度,简称时间复杂度。

  • 3.空间复杂度:一个程序的空间复杂度是指运行完一个程序所需内存的大小。程序执行时所需存储空间包括以下两部分。 (1)固定部分。这部分空间的大小与输入/输出的数据的个数多少、数值无关。主要包括指令空间(即代码空间)、数据空间(常量、简单变量)等所占的空间。这部分属于静态空间。(2)可变空间,这部分空间的主要包括动态分配的空间,以及递归栈所需的空间等。这部分的空间大小与算法有关。一个算法所需的存储空间用f(n)表示。S(n)=O(f(n)),其中n为问题的规模,S(n)表示空间复杂度

如何计算一个算法的时间复杂度

  • 1、不变复杂性
    1
    2
    3
    void print(String str) {
    Log.d("message",str); // 需要执行 1 次
    }

这个算法的时间复杂度T(n) = O(1),不管传入任何参数,代码只执行一遍

  • 2、线性复杂度
    1
    2
    3
    4
    5
    void print(int n) {
    for(int i = 0; i < n; i++) { // 需要执行 (n + 1) 次
    Log.d("message",i); // 需要执行 n 次
    }
    }

此时代码执行次数= n+1 +n = 2n + 1,那么当n无限大的时候 时间复杂度T(n) = O(n)

  • 3、平方阶复杂度
1
2
3
4
5
6
7
void print(int n) {
for(int i = 0; i < n; i++) { // 需要执行 (n + 1) 次
for(int j = 0; j < n; i++) { // 需要执行 n * n次
Log.d("message",i); // 需要执行 n * n 次
}
}
}

此时代码执行的次数为 n + 1+ nxn + nxn = 2n2 + n + 1 ,那么当n无限大的时候时间复杂度T(n) = O(n2)

  • 4、等等依次类推。空间复杂度也是如此。

总结

放图
image
image

知乎参考

stackoverflow参考


pv UV: