Big-O & Exact运行时
Big-O & Exact运行时
提问于 2018-06-28 20:09:07
我正在学习Big-O，虽然我开始理解一些东西，但我仍然不能正确地衡量算法的Big-O。我有一个代码：
int n = 10;
int count = 0;
int k = 0;
for (int i = 1; i < n; i++)
{
for (int p = 200; p > 2*i; p--)
{
int j = i;
while (j < n)
{
do
{
count++;
k = count * j;
} while (k > j);
j++;
}
}
}我必须测量Big-O和精确的运行时间。
首先，第一个for循环是O(n)，因为它依赖于n变量。第二个for循环是嵌套的，因此到目前为止使大O成为一个O(n^2)。
那么我们如何计算while (j < n) (所以到目前为止只有三个循环)，以及如果出现do while(k > j)，我们将如何计算它，生成4个循环，例如在本例中？一个全面的解释会很有帮助。谢谢。
回答 2
Stack Overflow用户
发布于 2018-06-28 20:58:58
除非我大错特错，否则这个程序有一个无限循环，因此它的时间复杂度无法有效地分析。特别是
do
{
count++;
k = count * j;
} while (k > j);一旦第二次进入此循环并执行count = 2，k将被设置为更大的j，并将无限期地保持此状态(忽略整数溢出，这将很快发生)。
我知道您正在学习Big-Oh符号，但是创建这样的玩具示例可能不是理解Big-Oh的最好方法。我建议阅读一本著名的算法教科书，在那里他们会带你了解新的算法，解释和分析他们所做的时间和空间的复杂性。
Stack Overflow用户
发布于 2018-06-29 18:23:14
我假设while循环应该是：
while (k < j)现在，在本例中，第一个for循环将花费O(n)时间。第二次循环将花费O(p)时间。现在，对于第三个循环，
int j = i;`
while (j < n){
...
j++;
}可以重写为
for(j=i;j<n;j++)这意味着它将花费O(n)时间。在最后一次循环中，k的值呈指数增长。将其视为与
for(k = count*j ;k<j ;j++,count++)因此，它将花费O(logn)时间。
总时间复杂度为O(n^2*p*logn)。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/51082561
复制相关文章
相似问题
腾讯云开发者
