一、基础概念
数据结构是计算机存储、组织数据的方式，指相互之间存在一种或多种特定关系的数据元素的集合。而算法是定义良好的计算过程，简单来说就是将输入转化为输出的一系列计算步骤。
我们用复杂度来衡量算法的优劣。复杂度分为时间复杂度（算法在时间上的效率）和空间复杂度（算法在空间上的效率）。我们更加关注时间复杂度，因为现在计算机的存储容量很大，不需要特别担心空间复杂度。
在计算机科学中，算法的时间复杂度是一个函数，它计算的是算法中基本操作的执行次数。
我们用大O的渐进表示法来大概估算算法的时间复杂度。比如O(N)、O(N^2)、O(N^3)等。这个表示方法只表示了最高次项，因为最高次项对算法时间复杂度的影响最大。N很小的时候没有比较的意义，因为CPU跑得很快。有多快？写个程序验证一下：
#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> int main() { int begin1 = clock(); int n = 100000000; int i = 0; int x = 10; for (i = 0; i < n; i++) { ++x; } int end1 = clock(); printf("%d\n", x); printf("%dms\n", end1 - begin1); int begin2 = clock(); n = 1000000; i = 0; x = 10; for (i = 0; i < n; i++) { ++x; } int end2 = clock(); printf("%d\n", x); printf("%dms\n", end2 - begin2); return 0; }可见，在Debug模式下循环中的语句执行1亿次，只用了26毫秒；而执行一百万次，只用了不到1毫秒。如果改成Release模式呢？
可见程序运行速度非常之快。
常见的时间复杂度的量级有以下这些：
| 5201314 | O(1) | 常数阶 |
| 3n+4 | O(n) | 线性阶 |
| 3n^2+4n+5 | O(n^2) | 平方阶 |
| 3log(2)n+4 | O(logn) | 对数阶 |
| 2n+3nlog(2)n+14 | O(nlogn) | nlogn阶 |
| n^3+2n^2+4n+6 | O(n^3) | 立方阶 |
| 2^n | O(2^n) | 指数阶 |
有些算法的事件复杂度存在最好、平均和最坏情况：最坏情况指的是任意输入规模的最大运行次数；平均情况是任意输入规模的期望运行次数；最好情况是任意输入规模下的最小运行次数。比如，在一个长度为N的数组中搜索一个数据x，最好的情况是1次找到，最坏情况是N次找到，平均情况是N/2次找到。实际情况中一般关注的是算法的最坏运行情况，所以数组中搜索数据的时间复杂度为O(N)。
二、例题
下面用两道leetcode面试题理解一下时间复杂度的概念。
第一个思路是先排序再依次查找，如果下一个值不等于前一个值+1，那么就找到了消失的数据。
用冒泡排序肯定是不行，因为它的时间复杂度是O(N)。快速排序也不行，时间复杂度是O(N*logN)。
第二个思路是0-N求和，再依次减去数组中的值，剩下的那个值就是消失的数字。这一思路是可以让时间复杂度达到O(N)的。这个思路的缺点是，如果N太大会发生溢出的情况。
int missingNumber(int* nums, int numsSize) { int N = numsSize; int ret = 0; ret = (0+N)*(N+1)/2; for(int i = 0;i<numsSize;i++) { ret -= nums[i]; } return ret; }第三个思路是利用按位异或。
0按位异或任何数都是这个数本身，任何数按位异或自己都是0；按位异或运算符合结合律。所以，我们把数组中的所有数都按位异或一遍；再把0-N的所有数都按位异或一遍，重复出现的数全都变成0，最后剩下的就是那个缺失的数字。
int missingNumber(int* nums, int numsSize) { int x = 0; for(int i = 0;i<numsSize;++i) { x ^= nums[i]; } for(int j = 0; j<= numsSize;j++) { x ^= j; } return x; }这样我们就达到了时间复杂度的要求。
再来一道：
这道题如果采用最简单暴力的方法，一次轮转1个位置，那么最少轮换0次，最多轮换(N-1)次，时间复杂度是O(N^2)。
void rotate(int* nums, int numsSize, int k) { k %= numsSize; while(k--) { int tmp = nums[numsSize-1]; for(int i=numsSize-2;i>=0;i--) { nums[i+1]=nums[i]; } nums[0]=tmp; } }这样是可以达到目的的，但是这个算法超过时间限制，在leetcode提交是过不了的。
怎么才能过呢？我们采用“三段逆置”的思路：
void swap(int* a, int* b) { int t = *a; *a = *b; *b = t; } void reverse(int* nums, int start, int end) { while (start < end) { swap(&nums[start], &nums[end]); start += 1; end -= 1; } } void rotate(int* nums, int numsSize, int k) { k %= numsSize; reverse(nums, 0, numsSize - k - 1); reverse(nums, numsSize - k, numsSize - 1); reverse(nums, 0, numsSize - 1); }这样时间复杂度就是O(N)，是可以通过的。
三、一些比较复杂的时间复杂度
void fun(int n) { int x = 0; for (int i = 1; i < n; i *= 2) { ++x; } printf("%d\n",x); } int main() { fun(8); fun(1024); return 0; }2^x = N ，因此以上这段代码的复杂度是O(logN)。（为了方便，时间复杂度中，以2为底时底数可以省略，其他底数也很少出现）
再来看看二分查找算法：
int binarySearch(int* nums, int x, int n) { assert(nums); int start = 0; int end = n - 1; while (start <= end) { int mid = start + ((end - start) >> 1); if (x > nums[mid]) { start = mid+1; } else if (x <nums[mid]) { end = mid-1; } else { return mid; } } return -1; } int main() { int nums[] = { 1,2,3,4,5,6,7,8,9 }; int find = binarySearch(nums, 5, 9); printf("%d\n", find); return 0; }最坏的情况是缩小到区间只有一个元素，或者没有找到此时x = log2N。所以这个算法的时间复杂度也是O(logN)。
二分查找因为时间复杂度低的特性，可以在巨量数据中快速找到要找的那个。但是，它只适用于有序数组结构，意味着想要插入或删除时需要挪动数据，很不方便。因此，二分查找在实际中很少使用。
END
