java- Big O符号

Question

所以，我试着解决一些大的问题，我遇到了一些麻烦。我不太明白他们的意思。例如，10MlogM + (N/2) log (N/2) + N/4和M log (N) + M log (M )的主要术语。我很难理解带有'log‘的大o表达式。任何帮助都将受到感谢，并提前表示感谢。

Answer 1

我在理解带有‘’的大o表达式时遇到问题

如果我们绘制它的图形，就很容易理解大O of log (或任何函数)：

​

​

现在，由于您面临的方程包含多个项(其中之一是log)，因此它可能会让您感到困惑。如果我们绘制第一项(我假设它是NlogN并丢弃常量(10))：

​

​

对于其他术语(N/2 * log(N/2))也是如此：

​

​

我相信你已经知道了，但这张图很容易证明，当我绘制整个函数的图时，只有主要术语(N logN)定义了大O (因为它只是为了显示函数的上界)：

​

​

N是什么意思？

此link通过此示例提供了非常好的解释：

O(n log n)：打印机的办公室搞错了，我们的电话簿的所有页面都是随机插入的。通过查看每一页上的名字，然后将该页放在新的空电话簿中的适当位置，来修正顺序，使其正确。

对于下面的示例，我们现在在打印机的办公室。电话簿正在等待邮寄给每个居民或企业，每个电话簿上都有一个贴纸，标明应该邮寄到哪里。每个人或每个企业都会得到一个电话簿。

O(n log n)：我们想要个性化电话簿，所以我们要在指定的副本中找到每个人或公司的名字，然后在电话簿上圈出他们的名字，并为他们的光顾写一封简短的感谢信。