计算时间算法的复杂性 [英] calculating time complexity of a algorithm

问题描述

可能重复：
  的纯英文解释，大澳

Possible Duplicate:
Plain English explanation of Big O

我一直在做编程工作4年了，但我从来没有支付重视到什么时间复杂度为紧密。我有一个面试的明天，我知道他们会问我关于it.Can任何问题，帮助我了解的时间复杂度简单来说有例子吗？通过查看code，我们怎么才能决定，如果它的复杂度为O（n）或O（log n）的O（N）等？

I have been doing programing for 4 years now, but i never paid attentions to what time complexity is closely. i have a interview tomorrow and i know they will be asking me questions on it.Can anyone help me understand time complexity in simple terms with example?By looking at the code how can we decide if its complexity is O(n) or O(log n) O(n) etc?

推荐答案

下面是一个普遍的建议：

Here is a general suggestion:

如果有一个单一的迭代和迭代变量线性递增那么它的O（N） 例如，

If there is a single iteration, and the iterative variable is incrementing linearly then it's O(n) e.g.

for(i=0;i<n;i++) //O(n)
for(i=0;i<n;i = i + 4) // still O(n)

如果迭代变量几何级数递增，那么它的O（log n）的

If the iterative variable is incremented geometrically, then it's O(log n)

例如

for(i=1;i<n;i = i * 2) //O(log n)

请注意的是，实现没有被使用循环，他们也许实现使用递归

Note that, the implementations don't have to be using loops, they maybe implemented using recursion.

如果有嵌套循环，其中一个有一个的O（n）和其他O（LOGN）的复杂性，则整体复杂度为O（nlogn）;

If there is nested loop, where one has a complexity of O(n) and the other O(logn), then overall complexity is O(nlogn);

例如

for(i=0;i<n;i++) // O(n)
 for(j=1;j<n;j=j*3) // O(log n)
//Overall O(nlogn)

这仅仅是一个手指交叉方针。在一般情况下，你必须有很好的概念，推导出复杂性。这就是为什么他们被要求，测试你的分析能力和理念。

This is only a finger cross guideline. In general, you have to have good concept to derive the complexity. That is why they are asked, to test your analytical ability and concept.

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