algorithm - 寻找算法的 Θ

Question

我有以下伪代码，它采用给定的长度为 size 的未排序数组，并通过查找数组中的最大值和最小值来查找范围。我只是在学习各种时间效率方法，但我认为下面的代码是 Θ(n)，因为较长的数组会添加固定数量的操作 (3)。

例如，忽略对 max 和 min 的实际赋值(因为未排序的数组是任意的，并且这些赋值事先是未知的)，长度为 2 的数组将总共只需要 5 个 Action (包括最终范围计算)。长度为 4 的数组总共只使用 9 个 Action ，再次添加最终范围计算。长度为 12 的数组使用 25 个 Action 。

这一切都指向 Θ(n)，因为它是线性关系。这是正确的吗？

伪代码:

// Traverse each element of the array, storing the max and min values
// Assuming int size exists that is size of array a[]
// Assuming array is a[]

min = a[0];
max = a[0];

for(i = 0; i < size; i++) {
    if(min > a[i]) {         // If current min is greater than val,
        min = a[i];        // replace min with val
    }

    if(max < a[i]) {         // If current max is smaller than val,
        max = a[i];        // replace max with val
    }
}

range = max – min;             // range is largest value minus smallest

Answer 1

你是对的。是 O(n)。

在简单代码(如上面的代码)中判断的一种简单方法是查看嵌套了多少 for() 循环(如果有)。对于每个“正常”循环(从 i = 0 -> n)，您添加一个因子 n。[Edit2]:也就是说，如果你有这样的代码:

array a[n]; //Array with n elements.
for(int i = 0; i < n; ++i){ //Happens n times.
    for(int j = 0; j < n; ++j){ //Happens n*n times.
        //something //Happens n*n times.
    }
}
//Overall complexity is O(n^2)

鉴于

array a[n]; //Array with n elements.
for(int i = 0; i < n; ++i){ //Happens n times.
    //something //Happens n times.
}
for(int j = 0; j < n; ++j){ //Happens n times.
    //something //Happens n times.
}
//Overall complexity is O(2n) = O(n)

这是非常初级的，但如果有人没有参加过算法类(class)，则很有用。

for() 循环中的过程与复杂性问题无关。

[编辑]:这假设大小实际上意味着数组 a 的大小。