时间戳

首页 > 解决方案 > 选择什么选择大哦符号

data-structures - 选择什么选择大哦符号

问题描述

n^2+nlog(n) 的大哦是多少？证明你的答案。如何选择大哦符号是 n^2 还是 nlog(n) 选择什么策略？

如果我选择 nlog(n) 我将如何解决它？

标签： data-structuresbig-o

解决方案

您似乎知道，当您对两个函数求和时，Big O 是“较大”函数（对于任意大的 n）的 Big O，所以我们只需要找出这两个函数中的哪一个。为此，我们可以解决以下限制：

  lim (n -> inf) n^2 / nlog(n)
= lim (n -> inf) n / log(n)
= lim (n -> inf) 1 / (1 / n) (L'Hopital's Rule)
= inf

这证明 n^2 是“更大”的函数，所以 O(n^2 + nlog(n)) = n^2

请注意，您也可以证明：

lim (n -> inf) nlog(n) / n^2 = 0

推荐阅读