c++ - 以下代码片段的时间复杂度是多少？

Question

我编写了以下代码片段来查找范围摘要，即，当给定一个没有任何重复项的排序整数数组时，它返回摘要如下:

/* IP: [0,1,2,4,5,7]
 * OP: ["0->2","4->5","7"]
 */

class Solution {
public:
    vector<string> summaryRanges(vector<int>& nums) {
        vector<string> res;

        if(nums.empty())
            return res;

        for(int i=0; i<nums.size(); i++) {
            int lowerRange=nums[i];

            while(((i+1)<nums.size()) && (nums[i+1]-nums[i]==1))
                i++;

            int higherRange=nums[i];

            if(lowerRange!=higherRange) {
                string str=to_string(lowerRange)+"->"+to_string(higherRange);
                res.push_back(str);
            } else
                res.push_back(to_string(lowerRange));
        }

        return res;
    }
};

我想知道上面代码片段的时间复杂度。在我看来，我正在为数组中的每个元素(使用外部 for 循环)执行一些“任务”(执行内部 while 循环)。因此，在我看来，在最坏的情况下，复杂度应该是 O(n^2)。另一方面，我很怀疑，因为我在内部 while 循环中执行 i++，因此，我不会对 所有 使用的元素执行“任务”外循环。由于这种增量，我在整个代码中只访问了一次所有元素。所以，这应该使复杂度为 O(n)。有人可以确认复杂度是 O(n^2) 还是 O(n)？

Answer 1

由于内循环推进与外循环相同的迭代变量，内循环访问的任何元素都被外循环跳过。他们一起只访问每个元素一次。所以这使得它成为 O(n)。

就时间复杂度而言，它就像一个包含 if 语句的循环:

for (i = 0; i < nums.size(); i++) {
    if ((i+1)<nums.size()) && (nums[i+1]-nums[i]==1)) {
        //
    } else {
        //
    }
}

以这种方式编写将需要不同的逻辑来确定何时更新 lowerRange 和 higherRange。