解释时间复杂度? [英] Explain Time Complexity?
问题描述
如何找到用 N 和 Big-O 表示的给定算法的时间复杂度?例如，
How does one find the time complexity of a given algorithm notated both in N and Big-O? For example,
//One iteration of the parameter - n is the basic variable
void setUpperTriangular (int intMatrix[0,…,n-1][0,…,n-1]) {
for (int i=1; i<n; i++) { //Time Complexity {1 + (n+1) + n} = {2n + 2}
for (int j=0; j<i; j++) { //Time Complexity {1 + (n+1) + n} = {2n + 2}
intMatrix[i][j] = 0; //Time complexity {n}
}
} //Combining both, it would be {2n + 2} * {2n + 2} = 4n^2 + 4n + 4 TC
} //O(n^2)
这个 O(n^2) 和 4n^2 + 4n + 4 的时间复杂度是多少?如果没有，您是如何得出答案的?
Is the Time Complexity for this O(n^2) and 4n^2 + 4n + 4? If not, how did you get to your answer?
另外，我有一个关于具有时间复杂度的二参数矩阵的问题.
Also, I have a question about a two-param matrix with time complexity.
//Two iterations in the parameter, n^2 is the basic variable
void division (double dividend [0,…,n-1], double divisor [0,…,n-1])
{
for (int i=0; i<n; i++) { //TC {1 + (n^2 + 1) + n^2} = {2n^2 + 2}
if (divisor[i] != 0) { //TC n^2
for (int j=0; j<n; j++) { //TC {1 + (n^2 + 1) + n^2} = {2n^2 + 2}
dividend[j] = dividend[j] / divisor[i]; //TC n^2
}
}
} //Combining all, it would be {2n^2 + 2} + n^2(2n^2 + 2) = 2n^3 + 4n^2 + 2 TC
} //O(n^3)
这会是 O(N^3) 和 2n^3 + 4n^2 + 2 吗?再说一遍，如果不是，有人能解释一下原因吗?
Would this one be O(N^3) and 2n^3 + 4n^2 + 2? Again, if not, can somebody please explain why?
推荐答案
您在大 O 时间复杂度中寻找的是一条指令执行的大致次数.因此，在第一个函数中，您有可执行语句:
What you're looking for in big O time complexity is the approximate number of times an instruction is executed. So, in the first function, you have the executable statement:
intMatrix[i][j] = 0;
由于可执行语句每次花费相同的时间，所以它是 O(1).因此，对于第一个函数，您可以将其缩减为如下所示，然后从可执行语句返回:
Since the executable statement takes the same amount of time every time, it is O(1). So, for the first function, you can cut it down to look like this and work back from the executable statement:
i: execute n times{//Time complexity=n*(n+1)/2
j: execute i times{
intMatrix[i][j] = 0; //Time complexity=1
}
}
回过头来，i 循环执行 n 次，j 循环执行 i 次.例如，如果 n = 5，则执行的指令数为 5+4+3+2+1=15.这是一个等差数列，可以用 n(n+1)/2 表示.因此该函数的时间复杂度为 n(n+1)/2=n^2/2+n/2=O(n^2).
Working back, the both the i loop executes n times and the j loop executes i times. For example, if n = 5, the number of instructions executed would be 5+4+3+2+1=15. This is an arithmetic series, and can be represented by n(n+1)/2. The time complexity of the function is therefore n(n+1)/2=n^2/2+n/2=O(n^2).
对于第二个函数，您正在查看类似的内容.您的可执行语句是:
For the second function, you're looking at something similar. Your executable statement is:
dividend[j] = dividend[j] / divisor[i];
现在，这个语句有点复杂，你可以从 wikipedia 中看到，教科书长除法的复杂度是 O(n^2).但是，被除数和除数不使用您的变量 n，因此它们不依赖于它.我们将被除数和除数称为矩阵m"的实际内容.所以可执行语句的时间复杂度是O(m^2).继续简化第二个函数:
Now, with this statement it's a little more complicated, as you can see from wikipedia, complexity of schoolbook long division is O(n^2). However, the dividend and divisor DO NOT use your variable n, so they're not dependent on it. Let's call the dividend and divisor, aka the actual contents of the matrix "m". So the time complexity of the executable statement is O(m^2). Moving on to simplify the second function:
i: execute n times{ //Time complexity=n*(n*(1*m^2))=O(n^2*m^2)
j: execute n times{ //Time complexity=n*(1*m^2)
if statement: execute ONCE{ //Time complexity=1*m^2
dividend[j] = dividend[j] / divisor[i]; //Time complexity=m^2
}
}
}
逆向工作，可以看到内部语句将花费 O(m^2)，并且由于 if 语句每次花费的时间相同，因此其时间复杂度为 O(1).你的最终答案是 O(n^2m^2).由于除法在现代处理器上花费的时间很少，因此通常估计为 O(1)(参见 this 以更好地解释为什么会这样)，您的教授可能正在为第二个函数寻找 O(n^2).
Working backwards, you can see that the inner statement will take O(m^2), and since the if statement takes the same amount of time every time, its time complexity is O(1). Your final answer is then O(n^2m^2). Since division takes so little time on modern processors, it is usually estimated at O(1) (see this for a better explanation for why this is), what your professor is probably looking for O(n^2) for the second function.
这篇关于解释时间复杂度?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
