确定while循环内部的函数的大-O

对于循环中循环内部的这种函数aFunction（）具有O（nlog（n））的大-o，如何确定最坏情况下的时间复杂度？确定while循环内部的函数的大-O

i ← 0 
while (i < n) 
    aFunction(...) 
    i ← i+1 
done

什么是论据，他们是否依赖于像'我'或'n'这样的东西？您的代码示例太薄 – Leeor

由于它涉及算法时间复杂性并且不涉及实际的代码，因此这看起来是无关紧要的。改为考虑cs.stackexchange.com。 – dg99

想想这里做了多少工作。每拨打aFunction需要时间O（n日志n），你总共调用n次。总的来说，这使得总共有O个工作（总共工作时间为0天）。

希望这会有所帮助！

2015-01-15 23:01:39 templatetypedef

不是这么简单。每个呼叫都需要'O（i log i）'。所以为了确保你是对的，我们必须把所有的'i log i'从i = 1到n。（如果我正确理解OP的问题） – Everv0id

@ Everv0id从提供的伪代码中，我无法判断每次迭代时是否在'i'或'n'上调用'aFunction'。我认为这是'n'，但你说得对，如果每次迭代都是'我'，那么这里需要更多的数学。 – templatetypedef

回答