时间复杂度讲解

一、基础概念数据结构是计算机存储、组织数据的方式指相互之间存在一种或多种特定关系的数据元素的集合。而算法是定义良好的计算过程简单来说就是将输入转化为输出的一系列计算步骤。我们用复杂度来衡量算法的优劣。复杂度分为时间复杂度算法在时间上的效率和空间复杂度算法在空间上的效率。我们更加关注时间复杂度因为现在计算机的存储容量很大不需要特别担心空间复杂度。在计算机科学中算法的时间复杂度是一个函数它计算的是算法中基本操作的执行次数。我们用大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模式呢可见程序运行速度非常之快。常见的时间复杂度的量级有以下这些5201314O(1)常数阶3n4O(n)线性阶3n^24n5O(n^2)平方阶3log(2)n4O(logn)对数阶2n3nlog(2)n14O(nlogn)nlogn阶n^32n^24n6O(n^3)立方阶2^nO(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 (0N)*(N1)/2; for(int i 0;inumsSize;i) { ret - nums[i]; } return ret; }第三个思路是利用按位异或。0按位异或任何数都是这个数本身任何数按位异或自己都是0按位异或运算符合结合律。所以我们把数组中的所有数都按位异或一遍再把0-N的所有数都按位异或一遍重复出现的数全都变成0最后剩下的就是那个缺失的数字。int missingNumber(int* nums, int numsSize) { int x 0; for(int i 0;inumsSize;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 inumsSize-2;i0;i--) { nums[i1]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 mid1; } 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