大循环错误条件

我只是需要一些澄清或帮助解决这个大问题。我不知道我是否正确地解释了这一点，但我注意到for循环有一个错误的条件，所以这意味着它不会循环。我的教授说可以确定循环的运行时间。所以我在想的是这样的：大循环错误条件

1 + (n - 1 - n) * (n) = 1 + 1 * n = 1 + n = O(n)

说明：1是用于循环以外的操作。（n - 1 - n）是外部循环的迭代，n是内部循环的迭代。

注意：我还在学Big O，所以如果我的任何逻辑错误，请纠正我。

int total = 0; 
for (int i = n; i < n - 1; i++) { 
    for (int j = 0; j < n; j++) { 
     total = total + 1 
    } 
}

来源

2016-10-15 Jasmine

什么是m和n？是m> n？ –

@ cricket_007我的歉意，m是打字错误，应该是n。我现在要解决这个问题。 – Jasmine

好吧，外环不运行。它没有运行时间 –

大O分析中不应该有任何负数。对于负面运行时间没有意义。此外，(n - 1 - n)不只是为了O(1)。你的外层循环甚至不会进入一次迭代。因此，循环中任何语句的时间复杂性都无关紧要。

总之，运行时间为1 + 1 = O(1)。

来源

2016-10-15 02:31:54

哦，我在计算中看到了我的错误，非常感谢您的理解！我最初的想法是O（1），因为你和我只是考虑循环之外的操作。但是我想当我的教授说运行时间来自循环时，它让我困惑。谢谢你的帮助！ – Jasmine

大O符号来描述函数的渐近行为。基本上，它告诉你函数增长有多快或者下降

例如，当分析某些算法时，可能会发现完成大小为n的问题所需的时间（或步骤数）由

T（N）= 4 N^2 - 2 N + 2

如果我们忽略常数（这很有意义，因为那些依赖于程序上运行特定的硬件）和生长较慢术语，我们可以说“T（n）”以n^2的顺序增长并且写成：T（n）= O（n^2）

对于形式定义，假设f（x）和g（x）是定义在实数的某个子集上的两个函数。我们写

F（X）= O（G（X））

（或F（X）= O（G（X））对于x - >无限远更精确）当且仅当存在常数N和C以使得

| f（x）| < = C | g（x）|对于所有的x>Ñ

直观上，这意味着，F不生长比克更快

如果是一些实数，我们写

F（X）= O（克（X））为X->一个

，当且仅当存在D> 0和C常数，使得

| f（x）| < = C | g（x）|对于| x-a |的所有x < d

因此，对于您的情况，这将是O（n^2）as | f（x）| > C | g（x）|从http://web.mit.edu/16.070/www/lecture/big_o.pdf

int total = 0; 
for (int i = n; i < n - 1; i++) { // --> n loop 
    for (int j = 0; j < n; j++) { // --> n loop 
     total = total + 1; // -- 1 time 
    } 
}

参考}

大O符号给出了一个假设，当值非常大外环将运行n次，内循环运行N次

采取N个 - > 100 总数n^2 10000运行时间

来源

2016-10-15 02:44:53 SarthAk

对不起，我很困惑你是如何到达O（n^2）我的问题。你能再解释一下吗？ – Jasmine

这样可以解决实际问题，并且在讨论big-O时很可能已经教过了。该帖子询问了所显示的代码，而不是 –

更新的答案的详细说明 – SarthAk

大循环错误条件

回答

相关问题