0

我编写了一个函数，它接受一个整数向量，并返回两个元素之间的最小差异（即，彼此最接近的元素的差异）。

我正在尝试计算算法的复杂性。第一个 for 循环遍历输入的所有元素（我称之为 N），这是线性复杂度：O(n)。内部 for 循环第一次迭代 N - 1，然后是 N - 2, N - 3, ... N - N + 2, N - N + 1, 0。所以我认为这个算法不是 O( n^2)。我的猜测是 O(N * log(N))，对吗？

#include <cstdlib>
#include <vector>

long int function(const std::vector<int> &Input)
{
    long int MinimumDifference = -1;

    for(size_t i = 0; i < Input.size(); i++)
    {
        for(size_t j = i + 1; j < Input.size(); j++)
        {
            long int Difference = abs(static_cast<long int>(Input[i] - Input[j]));
            if(Difference < MinimumDifference || MinimumDifference < 0)
            {
                MinimumDifference = Difference;
            }
        }
    }

    return MinimumDifference;
}

编辑： 所以上面是O（n ^ 2），认为我可以通过首先对列表进行排序来实现O（N * log（N））（使用std :: sort，它有O（N * log（N））） ，然后只遍历列表以找到最小的差异。

#include <cstdlib>
#include <vector>
£include <algorithm>

void function(const std::vector<int> &Input)
{
    std::vector<int> SortedInput = Input;
    std::sort (SortedInput.begin(), SortedInput.end());

    long int MinimumDifference = -1;

    for(size_t i = 0; i < SortedInput.size() - 1; i++)
    {
        long int Difference = abs(static_cast<long int>(SortedInput[i] - SortedInput[i + 1]));
        if(Difference < MinimumDifference || MinimumDifference < 0)
        {
            MinimumDifference = Difference;
        }
    }

    return MinimumDifference;
}
4

2 回答 2

3

一点代数操作告诉我们

(n-1) + (n-2) + ... + 1 = n * (n+1) / 2
                        = n^2 / 2 + O(n)

所以这个算法的复杂度确实是O(n^2)

于 2013-11-07T08:53:37.623 回答
0

不，你正在重叠两个“大致相同大小”的循环，你的复杂性是O(n^2/2) =O(n^2)

为了说服自己，想想sum(i) for i in [0,n] = n.(n+1)/2 = O(n^2/2) = O(n^2)这正是你在做什么。

要为新手做一些“复杂性”，只需计算叠瓦循环的数量即可。如果他们在基本元素上迭代，乘以n，如果他们将问题复杂性降低一个顺序（将问题分成两半），乘log(n)

于 2013-11-07T08:53:45.107 回答