寻找时间复杂 [英] finding the time complexity

问题描述

我想了解在复杂的细微差别 下面的每一个例子。

I am trying to understand the subtle difference in the complexity of each of the examples below.

int sum = 0;
for (int i = 1; i < N; i *= 2)
   for (int j = 0; j < N; j++)
      sum++;

我的分析：

第一个for循环也适用于LG n次。
内循环是独立的外循环并执行每一次N次外循环的执行。

The first for loop goes for lg n times.
The inner loop is independent of outer loop and executes N times every time outer loop executes.

所以复杂性必须是：
N + N + N ... LG n次

So the complexity must be:
n+n+n... lg n times

因此​​，复杂性是ñLGñ。

这是正确的？

int sum = 0;
for (int i = 1; i < N; i *= 2)
   for(int j = 0; j < i; j++)
      sum++;

我的分析：

第一个for循环也适用于LG n次。
内循环执行依赖于外部循环。

The first for loop goes for lg n times.
The inner loop execution depends on outer loop.

那么，如何计算的复杂性时，没有次内部循环执行依赖于外部循环？

So how do I calculate the complexity when no of times inner loop executes depends on outer loop?

int sum = 0;
for (int n = N; n > 0; n /= 2)
   for (int i = 0; i < n; i++) 
      sum++;

我想，例如C和例B必须有相同的复杂性，因为没有任何的时间内循环执行依赖于外部循环。

I think example C and example B must have same complexity because no of times the inner loop executes depends on outer loop.

这是正确的？

推荐答案

在实例B和C，内部循环的执行 1 + 2 + ... + N / 2 + N 次。这里恰好是 LGñ此序列来讲，这确实意味着 INT I = 0 执行 LGñ倍，但是总和在内部循环语句（s）是 2N 。所以，我们得到 O（N + LG N）=为O（n）

In examples B and C, the inner loop executes 1 + 2 + ... + n/2 + n times. There happen to be lg n terms in this sequence, and that does mean that int i = 0 executes lg n times, however the sum for the statement(s) in the inner loop is 2n. So we get O(n + lg n) = O(n)

这篇关于寻找时间复杂的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！