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

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

time-complexity algorithm c++

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

我正在解决一个问题 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 回复 | 直到 6 年前

meowgoesthedog 6 年前

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

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

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

Gilles 'SO- stop being evil' 6 年前

每次执行内部循环的主体时, 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()) 。

推荐文章

SkyWalker · 在JavaScript中,合并日期-时间序列的有效算法是什么?

1 年前

root · 计数算法

1 年前

André Silveira · 使用循环将数组的每个槽递增1。数组的大小是传递给函数的参数

2 年前

danial · 如何在多个字符串的每个位置找到最频繁的字符

2 年前

Manny · 如何比较Perl中的字符串?

2 年前

Suhail Gupta · 在排序阵列中查找目标范围的时间复杂度-此解在最坏情况下是否为O(N)?

2 年前

Diret · 获取范围内每个数字的子倍数的算法

2 年前

Saif · 排序时python如何决定何时调用比较器?

2 年前

TryingToLearn · 我如何为通用遥控器构造一个类,该遥控器向连接到它的各种设备发送开/关命令?

2 年前

Sneha Sharma · 滑动窗口-在我的代码中找不到错误(非常基本的算法)

2 年前