是 O(NlogN) 还是 O(N^2)？

Question

我正在尝试解决 BinarySearch.com 上的问题：

Given a list of integers nums sorted in ascending order and an integer k, return whether any two elements from the list add up to k. You may not use the same element twice. Note: Numbers can be negative or 0. This should be done in O(1) space.
So for nums = [1, 3, 5, 8] and k = 6, answer should be true.

我知道可以使用两个指针来完成，但我正在学习二进制搜索，所以我想出了以下逻辑：

bool solve(vector<int>& nums, int k) {
    for(int i=0; i<nums.size(); i++) {
        auto loc=lower_bound(begin(nums), end(nums), k-nums[i]);
        if(loc!=nums.end()) {
            if(distance(nums.begin(), loc)!=i && *loc+nums[i]==k) return true;
        }
    }
    return false;
}

它被接受了，但是时间复杂度是多少？我不确定它是否是 O(NlogN)，因为我对 nums 中的每个值进行了 运行 二进制搜索（O(logN) 算法），或者它是否应该是 O(N^2)因为当 if 条件为真时，我使用 distance()，据我了解，它本身就是一个 O(n) 操作。

Answer 1

如评论中所述，在最坏的情况下，代码会遍历数组并在每个步骤中对数组执行二进制搜索。所以这个操作的复杂度是 O(Nlog(N)).

I use distance(), which, as I understand, is an O(n) operation by itself.

实际上它在 std::vector::iterator 上使用时是 O(1) 因为它是一个 LegacyRandomAccessIterator（ ) and for such iterators std::distance is O(1) 所以它不参与我们的计算。