什么是我有两个for循环</p> <pre><code>for(int i = 2; i <= n/2; i++){ for(int j = 2 * i; j <= n; j++){ } } </code></pre> <p>什么是他们的时间复杂度的这类for循环

如果我将j ++更改为j + = i，该怎么办？如何计算迭代次数？

2016-10-23 codemonkey

不，它简化为O（N * N），因为每个你有n个N/2外循环（n减常数简化到n）内部循环。这种类型的问题对于StackOverflow来说并不是很合适，而且对于其他一些StackExchange站点比如http://cs.stackexchange.com/ – Slai

仍然O（n * n）更适合，因为n乘以一个常数可简化为n （'j + = i'在内部循环中是不变的）。如果你计算一些n值的循环次数，并在x-y轴上绘制，可能会更容易形象化https://en.wikipedia.org/wiki/Time_complexity – Slai

感谢Slai。我仍然有点困惑。我的想法是迭代将是n/2 +（n-3）/ 3 +（n-4）/ 4 +（n-5）/ 5 + .... +（n - （n - 1））/ （n - 1），那会是O（n * n）？我认为这可能是O（n） – codemonkey

-1

你是对的。时间复杂度为O（n）

2016-10-23 14:32:41 Nick

整体TC应为O(N^2)。

O(N)外圈和O(N)内圈。

2016-10-23 14:33:28

您可以有条不紊地进行，适马符号：

2016-10-25 16:23:01

回答