c++ - ベクトル内の値の最小差を計算するこの関数のアルゴリズムの複雑さは?

Question

私は、int のベクトルを取り、2 つの要素間の最小差 (つまり、互いに最も近い要素の差) を返す関数を作成しました。

アルゴリズムの複雑さを解決しようとしています。最初の 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））を達成できると思います（O（N * log（N））を持つs​​td :: sortを使用） 、そしてリストを反復して最小の違いを見つけます。

#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;
}