为什么O(n)优于O(nlog(n))? [英] Why is O(n) better than O( nlog(n) )?

问题描述

我只是遇到了这个奇怪的发现，在正常的数学中，n * logn小于n，因为log n通常小于1.那么为什么O(nlog(n))大于O(n)?(即为什么nlogn被认为比n花更多的时间)

Big-O是否采用其他系统?

解决方案

原来，我误解了Logn小于1.当我问几个年长者时，我今天就自己了解了这一点，即如果n的值很大(通常在考虑大O时，即最坏的情况)，那么logn可以大于1.

是的，O(1)＜O(登录)<O(n)＜O(nlogn)成立.

(我以为这是一个愚蠢的问题，也打算将其删除，但是后来意识到，没有问题是愚蠢的问题，可能会有其他人对此感到困惑，所以我把它留在了这里.)

I just came around this weird discovery, in normal maths, n*logn would be lesser than n, because log n is usually less than 1. So why is O(nlog(n)) greater than O(n)? (ie why is nlogn considered to take more time than n)

Does Big-O follow a different system?

解决方案

It turned out, I misunderstood Logn to be lesser than 1. As I asked few of my seniors i got to know this today itself, that if the value of n is large, (which it usually is, when we are considering Big O ie worst case), logn can be greater than 1.

So yeah, O(1) < O(logn) < O(n) < O(nlogn) holds true.

(I thought this to be a dumb question, and was about to delete it as well, but then realised, no question is dumb question and there might be others who get this confusion so I left it here.)

这篇关于为什么O(n)优于O(nlog(n))?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！