不了解与为log N

Question

显示大O符号是n /的log（n）+ 10 ×Ñ×的log（n ^5））= O（N /日志（n）的）

我很难解决这个问题。如果有人能向我解释为什么这是真的，那太棒了。

Answer 1

当您考虑函数复杂性的顺序时，可以删除乘法常量。所以n^2/logn + 10^5nlogn^5去n^2/logn + n logn^5。现在logn^5是5 logn所以辍学这个常数以及：n^2/logn + n logn。接下来，由于(n/logn)/logn随着n的增加而无限增长，所以n^2/logn项沼泽n logn，只剩下O(n^2/logn)。 （要看(n/logn)/logn无限期增长，请考虑(sqrt(n)/logn)^2。）