complexity-theory - 特定伪代码算法的复杂性

Question

我只是在为我的数据结构和算法期末学习。以下问题是我的期中考试，我弄错了，所以我只是想弄清楚：

以下伪代码的复杂度是多少？
 x <- 0
 for x <- 0 to n:
   for y <- 0 to n:
     y <- y + 1
     y <- y * 2

在期中我回答了 O( n^2 ) 但现在我再次查看它，我认为它可能是 O( nlogn ) .. 请参阅下面的答案显示我的尝试。

正确答案是什么？

任何帮助都可以帮助我通过考试！

干杯!

score 3 · Accepted Answer

以下是我暂时的回答...

外循环for x <- 0 to n肯定会执行 n 次。

内部循环for y <- 0 to n似乎执行了 n 次，但每次执行时，其包含的代码都会使 y 以指数方式接近 n。所以我相信这部分代码的执行复杂度为 O(logn)。

因此，整个算法的执行时间复杂度为 O(nlogn)。

score 0 · Accepted Answer

根据经验，我可能敢于这样表示您的算法的行为：

在此处输入图像描述

一些快照（“sum”是迭代次数）：

在此处输入图像描述

500 * 8 = 4000

在此处输入图像描述

2 回答 2