在列表中插入唯一数字的大 O 时间复杂度的证明

Question

我正在用 C++ 编写一个简单的循环，想知道时间复杂度是多少。

我的直觉告诉我它是 O(n*log(n)) 但我无法为 n*log(n)

提供证明

std::vector<int> nums{1,2,3,4,5,1,1,1,1,3,3,3,3}; 
std::vector<int> unique_nums; 
// get all unique nums
for(auto n: nums)
{
    if(std::find(unique_nums) != unique_nums.end())
    {
        unique_nums.push_back(n);
    }
}

这是我目前的理解。 std::find 是通过向量的线性时间搜索，但 unique_nums 向量的大小正以未知速率增长。

问题是：

我认为时间复杂度是O(n*log(n))
如果这是真的，是否有我可以应用的证明或公式？

Answer 1

最坏的情况是输入只有唯一数字。在这种情况下，等价于：

for(auto n: nums)
{
    std::find(unique_nums);   // we already know that it is not found
                              // because input is unique numbers
    unique_nums.push_back(n); // and we have to push_back anyhow
}

std::find 是 unique_nums 的线性大小，push_back 是摊销常数。总和 1 + 2 + .... + n 的首项是 n^2，因此我们可以说循环的复杂度是 O(nums.size()*nums.size()).

在列表中插入唯一数字的大 O 时间复杂度的证明

Proof for the time complexity in big O of a inserting unique numbers in a list

c++

time-complexity