代码之家 › 专栏 › 技术社区 › J. Doe

时间复杂度O(n)和非O(n^2)如何?

time-complexity algorithm c++

J. Doe · 技术社区 · 8 年前

我正在解决一个问题 LeetCode.com :

给定向量 nums 对于正整数,计算并打印子数组中所有元素的乘积小于k的(连续)子数组数。

代码(我在大量在线帮助下编写)如下:

class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        if(nums.empty() || k<=1) return 0;

        int counter=0, left=0, currProd=1;
        for(int i=0; i<nums.size(); i++) {
            currProd*=nums[i];
            while(left<nums.size() && currProd>=k)
                currProd/=nums[left++];
            counter+=i-left+1;
        }

        return counter;
    }
};

虽然我知道发生了什么,但我无法理解时间复杂性是如何被描述的 O(n) 而不是 O(n^2) 。IMHO,两个 i 和 left 将递增,从而访问 nums 在最坏的情况下,两次-一次通过感应变量 我 然后 左边 。

那么,时间复杂性如何呢 O(n) ?

2 回复 | 直到 8 年前

meowgoesthedog 8 年前

虽然代码看起来可能有欺骗性 O(N^2) -需要注意的关键是:

在for循环内, left 从不重置为0,并且在while循环中始终递增。

这意味着 while 循环最多只能执行 N 在 全部的 代码的执行。因此,代码只在数组中运行两次,因此 O(N) 。

Gilles 'SO- stop being evil' 8 年前

每次执行内部循环的主体时, left 增加1。 左边 初始值为0,且永远不会超过 nums.size() 。因此,最多执行内部循环的主体 nums。大小() 《泰晤士报》。

外部循环的主体被精确执行 nums。大小() 《泰晤士报》。

因此,函数的执行时间最多为 T0 + nums.size() * T1 + nums.size() * T2 其中T0是在外循环外执行代码所需的时间,T1是执行不包括内循环的外循环的一次迭代所需的时间,T2是执行内循环的一次迭代所需的时间。此上限的形式为 A + nums.size() * B 其中A和B是一些常数。因此,函数的执行时间为 O(nums.size()) 。

当您有两个嵌套循环时,整个程序的复杂性是最多 M*N 哪里 M 是外循环的迭代次数 N 是 最大限度 内部循环的迭代次数。因此,程序的复杂性满足 O(M*N) 。有时可能会找到一个下限,因为内部循环的迭代次数不同。这里,有一个不变量可以保证内部循环最多执行一定次数 全部的 ,它给出了比 O(nums.size() * nums.size()) 。

推荐文章

Matthew · 发现程序的时间复杂性

2 年前

TreasureGhost · 以下函数的时间复杂度是多少

2 年前

Abdullah Kassar · std::upper_bound()是线性的吗?c++

2 年前

user129393192 · 这个问题的最优算法是什么?

2 年前

3366784 · 使用序列初始化字符串的时间复杂度是多少?

2 年前

nehacharya · 这个代码的时间复杂度是O(n^2)还是O(nlogn)?

2 年前

control plane · ruby中链表上size调用的时间复杂性

2 年前

learner · 查找最长的子字符串

2 年前

hackrack · 在javascript中,如何返回时间复杂度为O(n)的相同字母元素?

8 年前

data-oil · 在字符串列表中搜索的高效快捷方法

8 年前