定义：
大O表示法是一种特殊的表示法，其用来指出算法的速度有多块
注意：大O表示法指出了最糟糕情况下的运行时间
原理对比：
1：对于普通的简单查找算法，如果有100个元素，最多需要猜测100次，如果有40亿个元素，最多需要40亿次，即最多需要猜测的次数与元素的个数成正比，被称为线性时间，即：O(n)
2：对于二分查找算法，100个元素最多需要猜测7次，而40亿的元素也仅仅最多需猜测32次，其运行时间为对数时间，即：O(logN)
增速对比：
下面做一个算法执行时间增速的实验：
采用简单的查找算法，我们知道，随着所需要查找元素个数的递增，所需要的时间也是呈线性递增的。
而对于二分查找，其随着查找元素的递增，所需要的查找时间的增速是很缓慢的。（摘自算法简介）
1
大O表示法指出了算法有多块，其并没有单位，即并非是指以秒为单位的，大O表示法让你能够比较操作数，用来指出算法运行时间的增速。
表示：
简单查询算法用大O表示法：O(N)
二分查找算法用大O表示法：O(logN)
N表示的是操作数
总结：
综上所述，我们知道了算法的速度指的并非时间，而是操作数的增速。在谈论算法的速度时，我们说的是随着输入数的增加，其运行时间将会以什么样的速度增加。
旅行商问题：
在计算机领域中有一个非常著名的旅行商的问题，其计算时间增加的非常快。
简介：有一位旅行商，需要前往5个城市，同时要保证旅程最短，故可考虑前往这些城市的所有可能顺序，对于每一种顺序，都计算出总旅程，再挑选出旅程最短的路线，5个城市就会有120种不同的排列方式。即5个城市需要120次操作，涉及6个城市时，需要720次操作，7个城市时，需要5040次操作。
综上涉及到n个城市时，需要执行n!（n的阶乘）次操作才能计算出最终需要的最短旅程路线。用大O表示法为O(N!)，即阶乘时间。
如果涉及的城市数量过多，会造成计算出结果时，太阳已经下山了...
网友评论