O(n log n)与O(log n)有何不同？
Ada*_*man 19 algorithm time big-o
研究大O表示法,我理解O(log n)作为二进制搜索的概念和O(n log n)作为快速排序.
任何人都可以用外行的术语说明这两者之间运行时的主要区别是什么？为什么会这样呢？
他们似乎在直觉上具有相似的相关性
Moo*_*uck 28
基本上:N因子.
二元搜索仅触及少量元素.如果有十亿个元素,则二进制搜索仅触及其中的~30个.
快速排序涉及每一个元素,少数几次.如果有十亿个元素,快速排序会触及所有这些元素,大约30次:总计约300亿次触摸.
- 二进制搜索在有序列表中找到一个值。快速排序是一种对列表进行排序的方法。它们之间并没有真正的关联。 (2认同)
dis*_*ame 26
看看它Log(n)是如何平坦(不是字面意义,而是比喻,与其他函数相比),而nLog(n)对于n = 100的值已经超过600.这就是它们的不同之处.
- 我看到这是一个有用的图表。 (2认同)