nlogn 是否与 n^2logn^2 相同
Is nlogn same as n^2logn^2
当我们计算Big O时，nlogn是否与n^相同2logn^2 ?（基本上当n换成n方块）
我今天和一位同事讨论这个问题，他提到 nlogn 算法的复杂度在 n 变成 n^2.
这听起来不正确。征求专家意见。
不，这不是真的。您可以查看两个函数的比率并评估渐近极限
n^2*log(n^2) = 2*n^2*log(n) (note that log(n^2) has the same oder as log(n))
ratio = [n*log(n)] / [2*n^2*log(n)] = 1/(2*n)
当n变大时，ratio趋于零，所以n*log(n)的阶数低于n^2*log(n^2)
您的朋友可能正在考虑 O(log n²) = O(log n) 这一事实。这意味着 O(n log n²) = O(n log n) 和 O(n² log n²) = O(n² log n)；但它 not 意味着 O(n² log n²) = O(n log n).
不，这显然不正确。
可能你的朋友感到困惑的是，对数中的指数可以变成乘数：log n² = 2 log n.这意味着 O(log n²) = O(2 log n )，并且由于乘法常数在 Big-O 中被删除，O(2 log n) = O(log n).
根据经验，在 Big-O 分析中可以丢弃对数内的指数。不过，这不适用于常规的非对数平方。
- O(log n²) = O(log n)
- O(n²) ≠ O(n)
- O(n² log n) ≠ O(n log n)
- O(n² log n²) = O (n² log n) ≠ O(n log n)
大的我们可以接下面的订单哦
1
从这个n^2是n的上限之一。所以 n 和 n2 的大 oh 不能相同。
当我们计算Big O时，nlogn是否与n^相同2logn^2 ?（基本上当n换成n方块）
我今天和一位同事讨论这个问题，他提到 nlogn 算法的复杂度在 n 变成 n^2.
这听起来不正确。征求专家意见。
不，这不是真的。您可以查看两个函数的比率并评估渐近极限
n^2*log(n^2) = 2*n^2*log(n) (note that log(n^2) has the same oder as log(n))
ratio = [n*log(n)] / [2*n^2*log(n)] = 1/(2*n)
当n变大时，ratio趋于零，所以n*log(n)的阶数低于n^2*log(n^2)
您的朋友可能正在考虑 O(log n²) = O(log n) 这一事实。这意味着 O(n log n²) = O(n log n) 和 O(n² log n²) = O(n² log n)；但它 not 意味着 O(n² log n²) = O(n log n).
不，这显然不正确。
可能你的朋友感到困惑的是，对数中的指数可以变成乘数：log n² = 2 log n.这意味着 O(log n²) = O(2 log n )，并且由于乘法常数在 Big-O 中被删除，O(2 log n) = O(log n).
根据经验，在 Big-O 分析中可以丢弃对数内的指数。不过，这不适用于常规的非对数平方。
- O(log n²) = O(log n)
- O(n²) ≠ O(n)
- O(n² log n) ≠ O(n log n)
- O(n² log n²) = O (n² log n) ≠ O(n log n)
大的我们可以接下面的订单哦
1 从这个n^2是n的上限之一。所以 n 和 n2 的大 oh 不能相同。