Big-O 分析作业：数据结构

Question

我是数据结构的新手 class，在我以前的 CS 课程中只稍微接触过 Big-O 的主题。我仍在网上了解它，但我只是想确保我做的是对的。关于Big-O分析有一些作业问题，我只是想和你们仔细检查一下。

以下是一些让我困惑的问题，以及我所做的分析：

//Part (a)
int x = 0;
for(int i = n; i >= 0; i--)             //N times
  if((i % 3) == 0) break;               //Executed O(N) times
    else x += n;                        //Executed O(N) times
Analysis: O(n)

//Part (b)
int x = 0;
for(int i = 0; i < n; i++)              //N times
  for(int j = 0; j < (n * n /3); j++)   //N^2 times
     x += j;                            //Executed O(N^3) times
Analysis: O(N^3)

//Part (c)
int x = 0;
for(int i = 0; i <= n; i++)             //N times
  for(int j = 0; j < (i * i); j++)      //N^2 times
     x += j;                            //Executed O(N^3) times
Analysis: O(N^3)

如果我的分析有误或到处都是，我很抱歉，我对这个概念还是很陌生！任何输入 and/or 的解释将不胜感激。谢谢！

Answer 1

a部分：循环最多执行3次。三是一个恒定的上限，所以复杂度是恒定的（又名O(1)）。

b 部分：您对这一点的看法是正确的。

C部分：在脑子里执行这个循环，根据i的值，想x += j运行多少次。如果 i 为零，则内循环将运行 0 次，如果 i 为一，则内循环将运行 1 次——通常，内循环将运行 i^2 (i 平方) 次。当我们计算整个事物（包括外循环）时，x += j 行将运行的总次数为：

0² + 1² + 2² + 3² + ... + (n - 1)² + n²

这个数学表达式等于(1/6)n(n + 1)(2n + 1)（see here），O((1/6)n(n + 1)(2n + 1))等于O(n^3)。所以你得到了正确的答案，但方法错误。

Big-O 分析作业：数据结构

Big-O Analysis Homework: Data Structure

algorithm

big-o

data-structures