渐近的对数函数的复杂性 [英] Asymptotic complexity of logarithmic functions

问题描述

我知道，在复杂性方面，O（LOGN）比为O（n），这比O（nlogn），这比O（N2）快了快了快。 但对于O（N2）和O（n2log），或O（n2.001）和O（n2log）：

I know that in terms of complexity, O(logn) is faster than O(n), which is faster than O(nlogn), which is faster than O(n2). But what about O(n2) and O(n2log), or O(n2.001) and O(n2log):

T1(n)=n^2 + n^2logn

什么是好大哦这个功能的欧米茄？此外，什么是小哦？ 对比：

What is the big Oh and omega of this function? Also, what's little oh? versus:

T2(n)=n^2.001 + n^2logn

有没有在大哦有什么区别呢？ 我无法理解如何用正的力量对比LOGN。如，是LOGN大约N R个0.000000 ...... 1或N ^ 1.000000 ...... 1？

Is there any difference in big Oh now? I'm having trouble understanding how to compare logn with powers of n. As in, is logn approximately n^0.000000...1 or n^1.000000...1?

推荐答案

为O（n ^ K）比更快的为O（n ^ķ '）所有 K，K'＆GT; = 0 和 K'＆GT;氏/ code>

O(n^k) is faster than O(n^k') for all k, k' >= 0 and k' > k

为O（n ^ 2）将快于为O（n ^ 2 * LOGN）

请注意，您只能忽略常数，没有涉及输入尺寸可以忽略不计。

Note that you can only ignore constants, nothing involving the input size can be ignored.

因此​​，的复杂性T（N）= N ^ 2 + N ^ 2logn 将是二，这是 0的差（ N R个2logn）。

Thus, complexity of T(n)=n^2 + n^2logn would be the worse of the two, which is O(n^2logn).

---

小哦

在松散的术语小哦，是有保证的上限。是的，它被称为小，并且它是更加严格。

Little oh in loose terms is a guaranteed upper bound. Yes, it is called little, and it is more restrictive.

N ^ 2 = O（N ^ K）为 K> = 2 ，但 N ^ 2 = O （N ^ K）为 K> 2

实际上，这是大哦这需要最出风头的。

Practically, it is Big-Oh which takes most of the limelight.

---

那么 T（N）= N ^ 2.001 + N ^ 2logn ？

我们有n个 ^2.001 = N ² * N ^0.001 和n ² *的log（n）。

We have n^2.001 = n²*n^0.001 and n² * log(n).

要解决这个问题，我们需要弄清楚什么的最终的更大，N ^0.001 或日志（N）。

To settle the question, we need to figure out what would eventually be bigger, n^0.001 or log(n).

事实证明，表格n的函数 ^K 与 K＆GT; 0 将最终接管的log（n）的足够的大 N 。

It turns out that a function of the form n^k with k > 0 will eventually take over log(n) for a sufficiently large n.

同样是这里的情况，从而 T（N）= O （N ^2.001 ）。

Same is the case here, and thus T(n) = O(n^2.001).

实际上不过，的log（n）将大于n ^0.001 。

Practically though, log(n) will be larger than n^0.001.

（10 ³³⁰⁰ ） ^0.001 ＆LT;日志（10 ³³⁰⁰ ）（1995.6＆LT; 3300），在这种情况下，足够大的n 将只是约10 ³⁶⁵⁰ ，一个天文数字。

(10³³⁰⁰)^0.001 < log(10³³⁰⁰) (1995.6 < 3300), and the sufficiently large n in this case would be just around 10³⁶⁵⁰, an astronomical number.

值得一提再次， 10 ³⁶⁵⁰ 。有 10 ⁸² 原子在宇宙中。

Worth mentioning again, 10³⁶⁵⁰. There are 10⁸² atoms in the universe.

这篇关于渐近的对数函数的复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！