时间复杂度
1.概念
时间复杂度表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度。
2.表示方法
T(n) = O(f(n))
n表示输入数据的规模大小，T(n)表示代码执行的时间，f(n)表示代码执行总次数的总和，O()表示T(n)与f(n)成正比。
3.时间复杂度分析
int cal(int n) {
int sum = 0;
int i = 1;
for (; i <= n; ++i) {
sum = sum + i;
}
return sum;
}
假设每一行普通的代码执行时间为time, 以上代码第二行和第三行执行时间分别为time1和time1，第三行和第五行的执行时间为timen和timen，所以执行总时间为(2+2n)*time，当n的值无限大的时候公式中低阶、常量和系数都可以忽略掉，所以上面代码的时间复杂度就可以表示为T(n) = O(n).
int cal(int n) {
int sum = 0;
int i = 1;
for (; i <= n; ++i) {
sum = sum + i;
}
return sum;
}
更具我们之前推导的方法，可以计算出执行总时间为(2+2n+3)*time，所以时间复杂度就表示为：T(n) = O(
)
int cal(int m, int n) {
int sum_1 = 0;
int i = 1;
for (; i < m; ++i) {
sum_1 = sum_1 + i;
}
int sum_2 = 0;
int j = 1;
for (; j < n; ++j) {
sum_2 = sum_2 + j;
}
return sum_1 + sum_2;
}
同分析得到以上代码的时间复杂度为O(m+n)。
4.常见时间复杂度
常量阶O(1)，线性阶O(n)，对数阶O(logn)，线性对数阶O(nlogn)，指数阶O()，阶乘阶O(n!)，平方阶O(
),k次方阶O(
)
可以分为：多项式量级和非多项式量级，其中非多项式量级只有指数阶O()和阶乘阶O(n!)
对数阶举例：
i=1;
while (i <= n) {
i = i * 2;
}
可以看出i的变化是一个等比数列，假设循环执行了x次，那么i==n，求解得到x=logn，所以时间复杂度表示为O(
)
i=1;
while (i <= n) {
i = i * 3;
}
类似的我们求出时间复杂度为 O()，但是
就等于
*
，去掉常量系数
，实际上也就表示为
，所以对数阶统一表示为 O(logn)
空间复杂度
1.概念
空间复杂度全称就是渐进空间复杂度（asymptotic space complexity），表示算法的存储空间与数据规模之间的增长关系。
2.表示方法
void print(int n) {
int i = 0;
int[] a = new int[n];
for (i; i <n; ++i) {
a[i] = i * i;
}
for (i = n-1; i >= 0; --i) {
print out a[i]
}
}
以上代码除了第三行的使用空间为n 的 int 类型数组，其它所占空间都为常量，所以整段代码的空间复杂度就是 O(n)。
我们常见的空间复杂度就是 O(1)、O(n)、O(n2 )，O(logn)、O(nlogn) 这样的对数阶复杂度平时都用用不到。
