0

我有几个我目前坚持的例子。非常感谢您的建议以及如何做到这一点。这些例子的最好和最坏情况是什么？

  • 示例 1

示例 1

  • 示例 2

示例 2

  • 示例 3

示例 3

4

2 回答 2

2

我不会给你答案的。但这里有一个例子，说明我将如何用评论来处理它。

for(int i = 0; i < N; i++) //This line is executed N times

    for(int j = i; j < N; j++) // This line is executed (N - i) times, for every N

         doSomeWorkOn(i, j);  //This can add complexity as well, but let's assume we're trying to figure out how many times this is called.

所以请注意，每次我们运行第一个循环时，我们在第二个循环中所做的工作量都会减少。这使事情复杂化。如果我们的内部循环读取

for(int j = 0; ......)

那么答案很简单，就是N*N。N次，我们需要做N量的工作。在这种情况下，我们拥有的是

N + (N-1) + (N-2)....(NN) 如果你再谷歌数学系列，你会发现这简化为 (N(N+1))/2。

编辑：

请注意，如果您与我所做的相反，则可能会更容易找到该系列，这意味着

0+1+2+...(N) = N + (N-1) + (N-2) ... (0) = (N(N+1))/2

第一种方法是最常见的。我有反向做的习惯，因为我记住了系列表，并且看到它与 N 的关系对我来说更有意义，但是从初学者的角度来看，你可能更容易从低端开始，因为这就是大多数帮助页面/教科书/教授将如何呈现它。然而，它是相同的。无论哪种方式对您来说都是最简单的。

于 2013-06-03T14:45:44.903 回答
1

对我来说，这看起来像是算法课的作业，但要分析迭代算法，您需要使用求和规则。Anany Levitin的《算法设计与分析导论》是一本好书。

并同意 ChrisCM 所说的 -

直接取自书中：时间效率

有用的规则：迭代算法分析

于 2013-06-03T14:48:37.827 回答