如果我有以下代码:
IterateArray(object[] array)
{
for(int i=0; i<array.length; i++)
{
Dosomething(array[i]);
}
}
并且Dosomething(object)
方法的时间性能是O(log n),整体性能是IterateArray
O(n)还是O(n log n)?
如果我有以下代码:
IterateArray(object[] array)
{
for(int i=0; i<array.length; i++)
{
Dosomething(array[i]);
}
}
并且Dosomething(object)
方法的时间性能是O(log n),整体性能是IterateArray
O(n)还是O(n log n)?
简短且有些错误的答案是 O(n log n)。
长答案:将其写为 O(n log m )会更准确。
除非 DoSomething 真的依赖于整个数组,否则它看起来像是在单个元素上运行。所以我们分别用“m”来区分。
这将是 O(n log n)
您正在执行 n 次 O(log n) 性能操作,并且乘法与 Big O 保持一致,因此 O(n) * O(log n) = O(n log n)
重要的是要注意,如果您正在查看两个不同大小的数组,则 m 和 n 之间实际上不需要任何区别。原因是 m 和 n 都是常数,如果要绘制它们的增长率,它们是渐近等效的。
O(n log n)
想想看 - 你正在执行 n 次 log n 操作。
对于 m 个对象中的每一个,如果 DoSomething() 的性能为 O(log n),那么所有 m 个对象的总性能将为 O(m log n)。
由于“for”循环迭代 n 次(例如数组长度为 n)次,并且在每次迭代中执行“Dosomething”,整体性能将是 O(n logn)。
干杯