4 algorithm complexity-theory big-o
例如,假设n = Integer.MAX_VALUE或2 ^ 123则O(log(n))= 32和123因此是一个小整数.不是O(1)？
有什么不同 ？我认为,原因是O(1)是常数但O(log(n))不是.还有其他想法吗？
Ste*_*sop 11
如果n超出上限,则涉及的复杂性类别n毫无意义.有作为没有这样的事情"的极限为2 ^ 123接近无穷大",除非是在老笑话,"一个五边形近似于圆形,对于5足够大的值".
通常,在分析代码的复杂性时,我们假设输入大小不受机器资源限制的限制,即使它是.这确实导致了一些稍微奇怪的事情周围发生的log n,因为如果n有适应一个固定大小的int类型,然后log n有相当小的束缚,所以绑定的更可能是有用/相关.
所以有时候,我们正在分析一个稍微理想化的算法版本,因为编写的实际代码不能接受任意大的输入.
例如,你的平均快速排序在最坏的情况下正式使用Theta(log n)堆栈,显然是这样的相当常见的实现,在分区的"小"方面调用recurses并在"big"方面循环recurses.但是在32位机器上你可以安排使用一个大约240字节的固定大小的数组来存储"待办事项列表",这可能比你根据正式有O的算法编写的其他函数要少. (1)堆栈使用.道德是实现!=算法,复杂性并没有告诉你关于小数字的任何信息,任何特定的数字都是"小".
如果要考虑边界,可以说,例如,对数组进行排序的代码是O(1)运行时间,因为数组必须低于适合PC地址空间的大小,因此对它进行排序的时间是有限的.但是,如果你这样做,你将失败你的CS任务,并且你不会向任何人提供任何有用的信息:-)