复杂度计算

复杂度一般指时间复杂度、空间复杂度，分别表现在代码的耗时和占用内存大小。
时间复杂度：执行常数时间操作的次数，指最坏的情况下：
空间复杂度：占用的内存空间；
复杂度用big O表示又称为渐进符号，是用于描述函数渐进行为的数学符号，当代码中出现int[] arr = new int[N];时我们可以说它的空间复杂度为O(N)。不同于空间复杂度的线性阶时间复杂度的表示有多种
算法复杂度 - 图1

  1. // O(1)
  2. int i = 1;
  3. int j = 2;
  4. int k = i + j;
  6. // O(log n)
  7. int i = 1;
  8. while(i<n)
  9. {
  10.     i = i * 2;
  11. }
  13. // O(n)
  14. int j = 1;
  15. for (int u = 0; u < n; u++) {
  16.    j++;
  17. }
  19. // O(n log n)
  20. for(m=1; m<n; m++)
  21. {
  22.     i = 1;
  23.     while(i<n)
  24.     {
  25.         i = i * 2;
  26.     }
  27. }
  29. // O(n^2)
  30. int j = 1;
  31. for(u=1; u<=n; u++){
  32.    for(m=1; m<=n; m++){
  33.        j++;
  34.     }
  35. }
  37. // O(2^n) 递归实现斐波那契数列
  38. int Fibonacci(int number)
  39. {
  40.     if (number <= 1) {
  41.         return number;
  42.     }
  43.     return Fibonacci(number - 2) + Fibonacci(number - 1);
  44. }

O(n!)的经典问题旅行商问题复杂度为O((n-1)!/2)
image.pngimage.png

复杂度速查

英文原文 https://www.bigocheatsheet.com/
中文转载
https://liam.page/2016/06/20/big-O-cheat-sheet/
https://www.cnblogs.com/lazyegg/p/12572421.html
image.pngimage.png
image.png
image.png

image.png
image.png
image.png