如何计算程序的时间复杂度？ [英] How to calculate the time complexity of a program?

问题描述

你能举个例子吗？谢谢！

Can you give an example?thanks!

推荐答案

请看我对这个问题的评论。时间复杂度不是计算的，不是用这个词的算术意义。我希望你明白，时间复杂性不会在几秒钟内完成。请参阅：

http://en.wikipedia.org/wiki/Time_complexity [< a href =http://en.wikipedia.org/wiki/Time_complexitytarget =_ blanktitle =New Window> ^ ]，

http://en.wikipedia.org/wiki/Big_O_notation [ ^ ]。



例如，对于（int index = 0; index< length; ++ index）{doSomething（index）; } 答案是O（n）。我们怎么知道的？因为，显然，对 doSomething 的调用次数以及因此时间是 length 的线性函数。当我们能够找出并分类这样的函数时，我们可以找到复杂性类。



显然它并不总是可能的。毕竟，已经证明可以创建具有不可预测行为的算法，因此找时间复杂度可能是理论上无法解决的问题，或者时间复杂性的概念可能根本不适用。

-SA

Please see my comment to the question. Time complexity is not calculated, not in arithmetical sense of this word. I hope you understand that time complexity is not measured in seconds. Please see:
http://en.wikipedia.org/wiki/Time_complexity[^],
http://en.wikipedia.org/wiki/Big_O_notation[^].

For example, for (int index = 0; index < length; ++index) { doSomething(index); } the answer is O(n). How do we know that? Because, apparently, the number of calls to doSomething and, hence, time, is a linear function of length. When we can figure out and classify such function, we can find out a complexity class.

It is also apparent that it's not always possible. After all, it is proven that it's possible to create an algorithm with unpredictable behavior, so finding time complexity may be a theoretically unresolvable problem, or the notion of time complexity may be not applicable at all.

—SA

这篇关于如何计算程序的时间复杂度？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！