时间复杂度
算法的时间复杂度是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷时的情况。
算法的时间复杂度，用来度量算法的运行时间，记作: T(n) = O(f(n))。它表示随着 输入大小n 的增大，算法执行需要的时间的增长速度可以用 f(n) 来描述。
时间复杂度计算
int func(int a){ cout << "hello-world" << endl;//执行1次 return 0;//执行1次 } //一共2次 int func2(int b){ for(int i = 0; i < n; ++i){//执行(n+1)次 cout << "hello-world" << endl;//执行n次 } return 0;//执行1次 } //一共(n + 1 + n + 1) = 2n + 2次
函数执行次数用T(n)表示，有了T(n)之后，在计算O(n)
T(n) = 5,时间复杂度为O(1) T(n) = n + 5，时间复杂度为O(n) T(n) = 3n^5, 时间复杂度为O(n^5) T(n) = 2n^3 + n^2 + 5,时间复杂度为O(n^3)
- 1.当 T(n) = c，c 为一个常数的时候，我们说这个算法的时间复杂度为 O(1)；如果 T(n) 不等于一个常数项时，直接将常数项省略。
- 2.取最高阶数项。
- 3.忽略与最高阶相乘的常数。
- 4.一个函数内有多个循环，取最大O(n)
void func(){ for(int i = 0; i < n; ++i)//O(n^2) for(int j = 0; j < n; ++j{ cout << "hello" << endl; } for(int k = 0; k < n; ++k){//O(n) cout << "hello" << endl; } } //时间复杂度为O(n^2)
空间复杂度
是指一个程序运行所需内存空间的大小。
程序执行时所需存储空间包括两部分：
- 固定部分：这部分空间的大小与输入、输出的数据的个数多少、数值无关，主要包括指令空间(代码空间)、数据空间(常量、变量)等所占用的空间，这部分属于静态空间。
- 可变空间：这部分空间主要包括动态分配的空间，以及递归栈所需的空间等，这部分的空间大小与算法有关。一个算法所需的存储空间用f(n)表示，S(n)=O(f(n)),其中n为问题的规模，S(n)表示空间复杂度。