给定一段代码的大O计算

Question

这些程序进行计算 ∑=0

我正在尝试进行大 O 计算。我做了很多研究，但我很难把它记下来。我知道大 O 是最坏的情况或上限。据我所知，一个程序有两个 for 循环，一个循环运行数组的长度，另一个运行到第一个循环的值，直到数组的长度。我认为如果两个运行数组的全长那么它将是二次 O(N^2)。因为第二个循环只运行数组长度的长度，所以我想 O(NlogN).

第二个程序只有一个 for 循环，所以它是 O(N)。

我接近了吗？如果不是，请向我解释我将如何计算。因为这是家庭作业，所以我将不得不在考试中算出这样的东西。

程序 1

// assume input array a is not null

public static double q6_1(double[] a, double x) 
{
    double result = 0;
    for (int i=0; i<a.length; i++) 
    { 
        double b = 1;
        for (int j=0; j<i; j++) 
        {
            b *= x;
        }
      result += a[i] * b;
    }
    return result;
}

节目 2

// assume input array a is not null

public static double q6_2(double[] a, double x) 
{
    double result = 0;
    for (int i=a.length-1; i>=0; i--) 
    {   
        result = result * x + a[i];
    }
    return result;
}

Answer 1

我使用 N 来指代数组的长度 a。

第一个是O(N^2)。内循环运行 1, 2, 3, 4, ..., N - 1 次。该总和约为 N(N-1)/2，即 O(N^2)。

第二个是O(N)。它只是遍历数组的长度。

Answer 2

程序的复杂性基本上是执行的指令数。

当我们谈论上限时，意味着我们正在考虑每个程序员都应该考虑的最坏情况。

让n = a.length;

现在回到你的问题，你说第一个程序的时间复杂度应该是O(nlogn)，这是错误的。当 i = a.length-1 时，内部循环也将从 j = 0 to j = i 迭代。因此复杂度为 O(n^2).

你判断第二个程序的时间复杂度是正确的O(n)。

给定一段代码的大O计算

Big O calculation given a piece of code

algorithm

big-o