如何确定算法函数的复杂度？
您如何知道算法函数对于特定操作是否需要线性/常数/对数时间？它取决于CPU周期吗？
How do you know if a algorithm function takes linear/constant/logarithmic time for a specific operation? does it depend on the cpu cycles?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
您可以通过三种方式（至少）做到这一点。
在网上查找算法，看看它是如何描述其时间复杂度的。
根据输入大小，自行检查算法，查看嵌套循环和递归条件等内容，以及每个循环运行或每次递归完成的频率。其扩展是严格的数学分析。
实验。改变输入变量，看看根据输入变量需要多长时间。计算一个方程，根据变量给出所述运行时间（对于 O(nc) 类型函数，联立方程求解是一种可能性。
其中，可能是第一个对于外行来说是最简单的，因为它几乎肯定是由更有知识的人做第二个:-)
There are three ways you can do it (at least).
Look up the algorithm on the net and see what it says about its time complexity.
Examine the algorithm yourself to look at things like nested loops and recursion conditions, and how often each loop is run or each recursion is done, based on the input size. An extension of this is a rigorous mathematical analysis.
Experiment. Vary the input variable and see how long it takes depending on that. Calculate an equation that gives you said runtime based on the variable (simultaneous equation solving is one possibility here for O(nc)-type functions.
Of these, probably the first is the easiest for the layman since it will almost certainly have been produced by someone more knowledgable doing the second :-)
起初，该函数可能需要任何时间来执行算法。它也可以是非常非线性的，甚至是无限的。
很快，如果你有一个算法，那么它就会使用称为图灵机的抽象。它用于测量在算法停止之前执行算法所需的操作数量。
您可以在这里获得更精确的信息WIKI::计算复杂性理论
At first the function may take any time to execute the algorithm. It can be quite non-linear also and even infinite.
Shortly if you have an algorithm then it is used the abstraction called Turing machine. It is used to measure a number of operations required to perform the algorithm before it halts.
More precise info you may get here WIKI::Computational complexity theory
关于CPU的依赖：
答案是否定的——时间复杂度完全与 cpu 无关。这是因为复杂性表明 - 算法对 CPU 资源的需求如何随着算法输入数据大小的增加而增加。换句话说，它是一个函数。而且功能在任何地方都是相同的 - 无论是在不同的机器上还是在不同的星球上:)
About dependency on CPU:
The answer is NO - time complexity is totally cpu independent. This is because complexity shows - How algorithm's demands on cpu resources increases with increasing algorithm input data size. In other words it is a function. And functions are the same everywhere - be it on different machines or on different planet :)