数据结构与算法：算法的时间复杂度
一个算法花费的时间与算法中语句执行次数成正比，哪个算法中语句执行次数多，它花费的时间就多。一个算法中语句的执行次数称为语句频度或时间频度。记为T(n).
//比如计算1到100所有数字之和，我们设计俩种算法： int count = 0; int end = 100; //该算法中使用了for循环，循环了100+1(最后一次判断), 时间频度为T(100)=100+1, 即T(n)=n+1 for(int i=1; i<=end; i++){ count+=i; } //而如果我们使用公式来计算，只需执行一次即可得到结果，时间频度为T(100)=1, 即T(n)=1 count = (1+end)*end/2
时间复杂度
在计算机科学中，时间复杂性，又称时间复杂度，算法的时间复杂度是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷时的情况。
大O符号
大O符号（Big O notation）是用于描述函数渐进行为的数学符号。更确切地说，它是用另一个（通常更简单的）函数来描述一个函数数量级的渐近上界。在数学中，它一般用来刻画被截断的无穷级数尤其是渐近级数的剩余项；在计算机科学中，它在分析算法复杂性的方面非常有用。
常数项可忽略
如下图, 2n+20和2n 、 3n+10和3n ，随着n值的增大，执行曲线无限接近，这时我们基本可忽略掉常数项：20、10
低次项可忽略
如下图，2n^2+3n+10和2n^2、n^2+5n+20和n^2，随着n值的增大，执行曲线无限接近，这时我们基本可以忽略掉低次项和常数项：3n+10、5n+20
系数可忽略
如下图, 3n^2+2n和5n^2+7n 随着n值的增大，执行曲线无限接近，这时我们基本可以忽略掉低次项：2n、5n，和系数：3、5
但是要注意的是，如果n的指数大于2时，它们的系数会对结果影响较大，如下图的 n^3+5n和6^3+4n，这种情况则不可以忽略系数
所以我们可以把时间频度T(n)=2n^2+3n+10忽略掉常数、低次项和系数，记成时间复杂度O(n^2)
常见的时间复杂度
-
常数阶O(1)
//无论代码执行了多少行，参数有多大，只要执行次数没有随着输入参数的变化而变化，那它的时间复杂度就是 O(1) int i = 1; int j = 2; ++i; j++; int m = i+j;
-
对数阶O(log2n)
//在while循环中，每循环一次i都会乘于2，当乘到x次时，i>n则退出循环，,所以while内的代码会执行x次，即i^x>n，又因为i每次的乘数是2即底数为2，所以它的时间复杂度是 (log2n), 如果乘数是3则是O(log3n) int i = 1; while(i<n){ i = i * 2; }
-
线性阶O(n)
//在for循环中，j=i会被执行n次，所以它的时间复杂度为O(n) int j = 0; for(int i=1; i<=n; i++){ j = i; }
-
线性对数阶O(nlog2n)
//线性对数对数阶则是将对数阶的代码再循环执行n遍，如果i的乘数为2,则时间复杂度为O(nlog2n) for(int m=1; m<=n; m++){ int i = 1; while(i<n){ i = i * 2; } }
-
平方阶O(n^2)
//平方阶则是将线性阶再循环执行n遍，记总共执行了n*n=n^2，所以它的时间复杂度为O(n^2) int num = 0; for(int i=1; i<=n; i++){ for(int j=1; j<=n; j++){ num = i+j; } }
-
立方阶O(n^3)
-
k次方阶O(n^k)
//立方阶和k次方阶参考平方阶，原理是一样的
-
指数阶O(2^n)
//因为时间复杂度为0(2^n)的算法开销过大，不推荐使用时间复杂度为0(2^n)的算法
平均时间复杂度和最坏时间复杂度
-
平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，该算法的运行时间。
-
最坏情况下的时间复杂度称最坏时间复杂度。一般讨论的时间复杂度均是最坏情况下的时间复杂度。 这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的界限，这就保证了算法的运行时间不会比最坏情况更长。
-
平均时间复杂度和最坏时间复杂度是否一致，和算 法有关(如图，以排序算法为例)。
空间复杂度
-
类似于时间复杂度的讨论，一个算法的空间复杂度(Space Complexity)定义为该算法所耗费的存储空间，它也是问题规模n的函数。
-
空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。有的算法需要占用的临时工作单元数与解决问题的规模n有关，它随着n的增大而增大，当n较大时，将占用较多的存储单元，例如快速排序和归并排序算法就属于这种情况
-
在做算法分析时，主要讨论的是时间复杂度。从用户使用体验上看，更看重的程序执行的速度。一些缓存产品(redis, memcache)和算法(基数排序)本质就是用空间换时间.
自动判断
中文
中文(简体)
中文(香港)
中文(繁体)
英语
日语
朝鲜语
德语
法语
俄语
泰语
南非语
阿拉伯语
阿塞拜疆语
比利时语
保加利亚语
加泰隆语
捷克语
威尔士语
丹麦语
第维埃语
希腊语
世界语
西班牙语
爱沙尼亚语
巴士克语
法斯语
芬兰语
法罗语
加里西亚语
古吉拉特语
希伯来语
印地语
克罗地亚语
匈牙利语
亚美尼亚语
印度尼西亚语
冰岛语
意大利语
格鲁吉亚语
哈萨克语
卡纳拉语
孔卡尼语
吉尔吉斯语
立陶宛语
拉脱维亚语
毛利语
马其顿语
蒙古语
马拉地语
马来语
马耳他语
挪威语(伯克梅尔)
荷兰语
北梭托语
旁遮普语
波兰语
葡萄牙语
克丘亚语
罗马尼亚语
梵文
北萨摩斯语
斯洛伐克语
斯洛文尼亚语
阿尔巴尼亚语
瑞典语
斯瓦希里语
叙利亚语
泰米尔语
泰卢固语
塔加路语
茨瓦纳语
土耳其语
宗加语
鞑靼语
乌克兰语
乌都语
乌兹别克语
越南语
班图语
祖鲁语自动选择
中文
中文(简体)
中文(香港)
中文(繁体)
英语
日语
朝鲜语
德语
法语
俄语
泰语
南非语
阿拉伯语
阿塞拜疆语
比利时语
保加利亚语
加泰隆语
捷克语
威尔士语
丹麦语
第维埃语
希腊语
世界语
西班牙语
爱沙尼亚语
巴士克语
法斯语
芬兰语
法罗语
加里西亚语
古吉拉特语
希伯来语
印地语
克罗地亚语
匈牙利语
亚美尼亚语
印度尼西亚语
冰岛语
意大利语
格鲁吉亚语
哈萨克语
卡纳拉语
孔卡尼语
吉尔吉斯语
立陶宛语
拉脱维亚语
毛利语
马其顿语
蒙古语
马拉地语
马来语
马耳他语
挪威语(伯克梅尔)
荷兰语
北梭托语
旁遮普语
波兰语
葡萄牙语
克丘亚语
罗马尼亚语
梵文
北萨摩斯语
斯洛伐克语
斯洛文尼亚语
阿尔巴尼亚语
瑞典语
斯瓦希里语
叙利亚语
泰米尔语
泰卢固语
塔加路语
茨瓦纳语
土耳其语
宗加语
鞑靼语
乌克兰语
乌都语
乌兹别克语
越南语
班图语
祖鲁语有道翻译
百度翻译
谷歌翻译
谷歌翻译（国内）翻译 朗读 复制 正在查询，请稍候…… 重试 朗读 复制 复制 朗读 复制 via 谷歌翻译（国内）译