2

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

例如，忽略和的实际分配max（min因为未排序的数组是任意的，并且这些分配是预先未知的），长度为 2 的数组总共只需要 5 个动作（包括最终范围计算）。长度为 4 的数组总共只使用 9 个动作，再次添加最终范围计算。长度为 12 的数组使用 25 个动作。

这一切都指向我Θ(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
4

4 回答 4

3

你是对的。是 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)

这是非常基本的，但如果有人没有上过算法课程，那么它很有用。

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

[编辑]：这假设 size 实际上是指数组 a 的大小。

于 2013-09-19T23:31:52.650 回答
3

是的，这将是 Θ(n)。不过你的推理有点歪。

您必须查看循环中的每个项目，以便您受到线性函数的限制。相反，您也受到线性函数的限制（实际上是相同的），因为您无法避免查看每个元素。

O(n) 只要求你在上面绑定，Omega(n) 要求你在下面绑定。Θ(n) 表示你在两边都有界。

于 2013-09-19T23:36:16.437 回答
2

让 size 为n，然后很清楚地看到你总是有2n比较，当然还有最后的单一分配。所以你总是2n + 1在这个算法中有操作。

在最坏的情况下，您有2n作业，因此 2n + 1 + 2n= 4n + 1= O(n)。

在最好的情况下，您有0分配，因此2n + 1 + 0= 2n + 1= Ω(n)。

因此，我们认为最好和最坏的情况都在线性时间内执行。因此，Ɵ(n)。

于 2013-09-19T23:33:53.017 回答
1

是的，这肯定是O(n)算法。我不认为你真的需要深入研究来查看比较次数来得出关于算法复杂性的结论。只需尝试查看比较次数将如何随着输入大小的增加而变化。对于O(n)比较应该随着输入的增加而线性增加。因为O(n^2)它增加了 n 的某个倍数，依此类推。

于 2013-09-19T23:34:04.283 回答