当n的值变得非常小时，会变成Big-O吗? [英] Big-O when the value of n gets very small?

问题描述

我错过了介绍big-O的课程，因为认为这很简单.但是，当n变得非常小时，老师似乎仍然对O(n)偏离函数有什么看法?我在书的任何地方都找不到.有人可以启发我吗?如果有意义的话，我们对O(n)的探索是在排序算法的背景下进行的.

I missed the class where big-O was introduced thinking that it was pretty straight forward. It still seems to be however the teacher said something about O(n) deviating from the function when n gets very small? I couldn't find this anywhere in the book. Could someone enlighten me? Our exploration of O(n) has been in the context of sorting algorithms if that is of any significance.

谢谢 基因

感谢您的帮助，它一直在照亮.我有一个后续问题.是否有一种相对简单的数学方法来找出n对于O(n)而言太小的点?

edit: Thanks for the help guys it has been illuminating. I have a follow-up question. Is there a relatively simple mathematical way to figure out the point where n is too small for O(n)?

相关问题

是否有O(1/n)算法?
Θ(n)和O(n)有什么区别?

推荐答案

Big O不会描述函数的执行时间，而只是描述增长时间.所有函数都有一定的常数因子或开销需要添加.当n低时，此开销会使该算法的任何改进都相形见--一种算法，每次操作需要50ms，但具有O(n)，对于小n而言，其性能会更差.而不是每次操作需要5毫秒但具有O(n * n)的算法.

Big O doesn't describe the execution time of a function, just the growth. All functions have some constant factor or overhead that needs to be added in. When n is low, this overhead can greatly dwarf any improvements to the algorithm - an algorithm that requires 50ms per operation but has O(n) will perform worse for small n than an algorithm that requires 5 ms per operation, but has O(n*n).

这就是为什么通常来说，对于小集合来说，大O并不重要.对于大多数具有简单比较的对象，对10个项目的快速排序显然不会比气泡式排序快，对100个项目的线性搜索可能比二叉树更快，依此类推.

This is why, in general, for small sets big O doesn't matter. For most objects with simple comparisons, a quick sort on 10 items will not be noticiably faster than a bubble sort, a linear search on 100 items will probably be faster than a binary tree, and so on.

这篇关于当n的值变得非常小时，会变成Big-O吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！