算法基础知识

算法的复杂度

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

Big O

image

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

• 1、不变复杂性

O（1）：称为不变复杂性

1项：1秒
10项：1秒
100个项目：1秒
项目的数量仍然增加10倍，但O（1）的比例因子总是1。

• 2、对数复杂度

O（log n）：称为对数复杂度

1项：1秒
10项：2秒
100项：3秒
1000项：4秒
10000项：5秒
计算次数只会增加输入值的对数。因此，在这种情况下，假定每个计算需要1秒钟，输入的日志n就是所需的时间log n。

• 3、线性复杂度

O（n）：称为线性复杂度

1项：1秒
10项：10秒
100个项目：100秒
这次项目数量增加了10倍，时间也增加了10倍。n = 10，所以O（n）的比例因子是10。

• 4、二次型复杂度

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)=Ｏ(f(n)),称Ｏ(f(n))为算法的渐进时间复杂度，简称时间复杂度。

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

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

• 1、不变复杂性

void print(String str) {
   Log.d("message",str);      //  需要执行 1 次
}

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

• 2、线性复杂度

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、平方阶复杂度

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 + nxn + nxn = 2n2 + n ，那么当n无限大的时候时间复杂度T(n) = O(n2)

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

总结

放图
[图片上传失败...(image-5a2bb0-1513698831175)]
[图片上传失败...(image-bff3cb-1513698831175)]

知乎参考

stackoverflow参考