代码之家 › 专栏 › 技术社区 › blazerix

为什么给定的算法是O(n^2)?

big-o math algorithm

blazerix · 技术社区 · 6 年前

我正在研究一个算法,试图将它分解,并为它提出一个大的O符号。但是,我无法推断为什么它是O(n^2)

我可以看到外环指向n,但内环将我抛向一边。

int a = 0;
for (i = 0; i < N; i++) {
    for (j = N; j > i; j--) {
        a = a + i + j;
    }
}

有人知道如果我在面试中突然出现这些问题,我如何才能最好地处理这些问题吗?我想更好地分析算法

2 回复 | 直到 6 年前

melpomene 6 年前

外部循环从 0 到 N-1 。

内部循环从 N 到 i+1 .

这意味着在外循环的第一次迭代中,内循环 n 步骤。在外部循环的第二次迭代中,内部循环 N-1 步骤。在外部循环的第三次迭代中,内部循环 N-2 步骤。…这将一直持续到外部循环的最后一次迭代,其中内部循环 1 步骤。

因此,步骤总数为 N + (N-1) + (N-2) + ... + 2 + 1 或(重新排列) 1 + 2 + ... + (N-1) + N . 这个和等于 N * (N+1) / 2 ( see here 详细信息),扩展到 0.5 * N^2 + 0.5 * N . 忽略较低的幂和常量因子意味着这是在o(n^2)中。

Eric 6 年前

如果你是一个视觉上的人,你可以把外部循环看作行,而把内部循环看作列。对于外部循环的每个迭代,内部循环中的迭代(列)数减少1。

通过视觉呈现,您可以获得:

* * * * * 
  * * * * 
    * * * 
      * * 
        *

这是半个正方形(三角形),所以大约是(n^2)/2,也就是o(n^2)。

推荐文章

Muhammad Umer · 为什么这个随机数猜谜游戏模拟产生5.8

5 月前

Matthew Thomas · 在每个决策中给出多个选择的所有可能的决策路径/结果

5 月前

Jack Maessen · 当min-val不为0时,如何计算输入type=“range”中点之间的填充颜色

6 月前

Alisa Petrova · 在有向图中更改一对顶点以创建循环

6 月前

Jukka · 计算中值

6 月前

D W · Python-将浮点数从2转换为10到100位小数

6 月前

Bartol · 确定python龟图形中的角度

11 月前

randomAlgo · 将弹簧设置为相同长度的成本最低

11 月前

Fyodor · 在C中使用sin和cos计算数学表达式不正确?

11 月前

Sergio · python中大量数字的乘法

11 月前