当n的值变得非常小时,Big-O？

Question

我错过了引入big-O的课程,认为这是非常直接的.然而,当n变得非常小时,教师似乎还在说一些关于O(n)偏离函数的东西？我无法在书中的任何地方找到这个.有人可以开导我吗？我们对O(n)的探索一直是在排序算法的背景下,如果它具有任何意义.

谢谢基因

编辑:感谢帮助人员,它一直很有启发性.我有一个后续问题.是否有一种相对简单的数学方法来确定n对于O(n)来说太小的点？

相关问题

有没有O(1/n)算法？
Θ(n)和O(n)之间有什么区别？

Answer 1

Big O没有描述函数的执行时间,只是增长.所有函数都有一些需要加入的常数因子或开销.当n很低时,这种开销会使算法的任何改进相形见绌 - 一种算法需要每次操作50ms但是O(n)对小n的性能会更差而不是每个操作需要5毫秒但是有O(n*n)的算法.

这就是为什么一般来说,对于小套装来说,大O并不重要.对于大多数具有简单比较的对象,对10个项目的快速排序不会明显快于冒泡排序,对100个项目的线性搜索可能比二叉树更快,依此类推.

Answer 2

Big-O表示法背后的概念是算法的渐近性能.随着N越来越大,Big-O表示法中的术语占据了总时间的主导地位.例如,在O(N ^ 2)算法中,总时间T(N)可能是:

T(N) = a * N * N + b * N + c

随着N越大越大,无论b或c的值如何,N ^ 2中的项都占主导地位.

但是,当N很小时,b和c项很重要.

例如,如果a = 0.001,b = 1,000,并且c = 1,000,000.

 N                ~ T(N) [1 significant figure]
 1                1,000,000                (almost all c)
 1,000            2,000,000                (50:50 split on b and c)
 1,000,000        2,000,000,000            (50:50 split on a and b)
 1,000,000,000    1,000,000,000,000,000    (almost all a)

因此,如果您忽略了低阶项,那么低N处的表现将完全被误传.在高N时,低阶项并不重要.

Answer 3

随着参加讲座的次数(N)变得非常小,课程材料变得难以理解.