易做文学网站的logo,工程建设标准强制性条文最新版本,辽阳网站推广,企业网站管理系统多站多语言版找个时间写一写时间复杂度和一些问题分类#xff0c;也普及一下这方面知识。
如何衡量一个算法好坏
很显然#xff0c;最重要的两个指标#xff1a;需要多久可以解决问题、解决问题耗费了多少资源
那我们首先说第一个问题#xff0c;要多长时间来解决某个问题。那我们可…找个时间写一写时间复杂度和一些问题分类也普及一下这方面知识。
如何衡量一个算法好坏
很显然最重要的两个指标需要多久可以解决问题、解决问题耗费了多少资源
那我们首先说第一个问题要多长时间来解决某个问题。那我们可以在电脑上真实的测试一下嘛多种方法比一比用时最少的就是最优的啦。
但是没必要我们可以通过分析计算来确定一个方法的好坏用O()表示括号内填入N、1等式子。
这到底是什么意思呢
简单来说就是这个方法时间随着数据规模变化而增加的快慢。时间可以当成Y数据规模是Xyf(x)就这样而已。但是f(x)不是准确的只是一个大致关系y10x,我们也视作x因为他的增长速度还是n级别的。现在就可以理解了一般O(N)就是对每个对象访问优先次数而已。请注意O(1)它不是每个元素访问一次而是Y1的感觉y不随x变化而变化数据多大它的时间是不变的有限的常数操作即可完成。
那我们就引入正规概念
时间复杂度是同一问题可用不同算法解决而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。
计算机科学中算法的时间复杂度是一个函数它定性描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述不包括这个函数的低阶项和首项系数。使用这种方式时时间复杂度可被称为是渐近的它考察当输入值大小趋近无穷时的情况。
注意文中提到不包括这个函数的低阶项和首项系数。什么意思呢就是说10n,100n,哪怕1000000000n,还是算做O(N)而低阶项是什么意思不知大家有没有学高等数学1里面有最高阶无穷大就是这个意思。举个例子。比如yn*n*nn*nn1000
就算做o(n*n*n),因为增长速率最大N*N及其它项增长速率慢是低阶无穷大n无限大时忽略不计。 那接着写o(n*n*n)的算法一定不如o(n)的算法吗也不一定因为之前说了时间复杂度忽略了系数什么意思o(n)可以是10000000n当n很小的时候前者明显占优。
所以算法要视实际情况而定。
算法的时间 复杂度常见的有 常数阶 O(1)对数阶 O(log n)线性阶 O(n) 线性对数阶 O(nlog n)平方阶 O(n^2)立方阶 O(n^3)… k 次方阶O(n^k)指数阶 O(2^n)阶乘阶 O(n!)。
常见的算法的时间 复杂度之间的关系为 O(1)O(log n)O(n)O(nlog n)O(n^2)O(2^n)O(n!)O(n^n) 我们在竞赛当中看见一道题第一件事就应该是根据数据量估计时间复杂度。
计算机计算速度可以视作10^9,如果数据量是10000你的算法是O(N*N)那就很玄10000*1000010000 0000别忘了还有常数项这种算法只有操作比较简单才可能通过。你可以想一想O(nlog n)的算法一般就比较稳了。那数据量1000一般O(N*N)就差不多了数据量更小就可以用复杂度更高的算法。大概就这样估算。 当 n 很大时指数阶算法和多项式阶算法在所需时间上非常 悬殊。因此只要有人能将现有指数阶算法中的任何一个算法化 简为多项式阶算法那就取得了一个伟大的成就。
体会一下 空间复杂度也是一样用来描述占空间的多少。
注意时间空间都不能炸。
所以才发明了那么多算法。
符上排序算法的时间空间表体会一下 排序博客加深对时间空间复杂度理解
https://blog.csdn.net/hebtu666/article/details/81434236 相关扩展https://blog.csdn.net/hebtu666/article/details/82465495
