1、时间|空间复杂度-概述

  1. 1、时间复杂度(Time Complexity[kəmˈpleksəti])
  2.     1-1、一个算法语句** 总的执行次数 **是关于问题规模N的某个函数,记为f(N)，N为问题的规模，算法语句总的执行次数记为T(N)，算法执行次数的增长速率和f(N)的增长速率相同。
  3.     1-2、T(N)=O(f(N)), 称为算法的渐进时间复杂度,简称为时间复杂度。
  4.     1-3、一个算法花费的时间与算法中语句的执行次数成正比，执行次数越多，花费的时间就越多，其执行次数称为语句频度或时间频度，记为T(n)。
  5.     1-4、算法中的语句执行次数为一个常数，则时间复杂度为O(1)
  6.     1-5、常用的时间复杂度有以下七种，算法时间复杂度依次增加：
  7.         O(1)常数型、O(log2 n)对数型、O(n)线性型、O(nlog2n)二维型、O(n^2)平方型、O(n^3)立方型、O(2^n)指数型.
  9. 2、空间复杂度(Space Complexity[kəmˈpleksəti])
  10.     2-1、指运行完一个程序所需内存的大小，利用程序的空间复杂度，可以对程序的运行所需要的内存多少有个预先估计。
  11.     2-2、程序执行时所需存储空间包括以下两部分。 
  12.         2-2-1、固定部分：这部分空间的大小与输入/输出的数据的个数多少、数值无关，主要包括指令空间(即代码空间)、数据空间(常量、简单变量)等所占的空间，这部分属于静态空间。 
  13.         2-2-2、可变空间：这部分空间的主要包括动态分配的空间，以及递归栈所需的空间等，这部分的空间大小    2-3、与算法有关。一个算法所需的存储空间用f(n)表示。S(n)=O(f(n))，其中n为问题的规模，S(n)表示空间复杂度。

1.1、时间|空间复杂度-注意点

  1. 1、空间复杂度是对一个算法在运行过程中** 临时占用存储空间大小 **的量度。
  2. 2、通常来说，只要算法不涉及到动态分配的空间以及递归、栈所需的空间，空间复杂度通常为0(1)。
  3. 3、算法的空间复杂度并不是计算实际占用的空间，而是计算整个算法的辅助空间单元的个数，与问题的规模没有关系。

2、时间|空间复杂度-表达式-简介

  1. O后面的括号中有一个函数，指明某个算法的耗时/耗空间与数据增长量之间的关系。其中的n代表输入数据的量。哈希算法就是典型的O(1)时间复杂度，无论数据规模多大，都可以在一次计算后找到目标（哈希冲突不考虑）
  2. O(1)：最低的时空复杂度，也就是耗时/耗空间与输入数据大小无关，无论输入数据增大多少倍，耗时/耗空间都不变。 
  3. O(n)：时间复杂度为O(n)，代表数据量增大几倍，耗时也增大几倍，比如常见的遍历算法。再比如时间复杂度O(n^2)，就代表数据量增大n倍时，耗时增大n的平方倍，这是比线性更高的时间复杂度。比如冒泡排序，就是典型的O(n^2)的算法，对n个数排序，需要扫描n×n次。
  4. O(logn)：当数据增大n倍时，耗时增大logn倍（这里的log是以2为底的，比如，当数据增大256倍时，耗时只增大8倍，是比线性要低的时间复杂度）。二分查找就是O(logn)的算法，每找一次排除一半的可能，256个数据中查找只要找8次就可以找到目标。
  5. O(nlogn)：同理，就是n乘以logn，当数据增大256倍时，耗时增大256*8=2048倍。这个复杂度高于线性低于平方。归并排序就是O(nlogn)的时间复杂度。

3、常见时间|空间复杂度及其增长速度-比较

  1. O(1)＜O(log n)＜O(n)＜O(nlog n)＜O(n^2)＜O(n^3)< O(2^n)＜O(n!)＜O(n^n)

4、排序算法-时间|空间复杂度-简介image.png