3和小的时间复杂度

Question

一个名为3和小 on LeetCode的问题问道：

给定一个n整数nums数组和一个target数组，找到满足条件nums[i] + nums[j] + nums[k] < target的具有0 <= i < j < k < n的索引三叉i, j, k的数目。 你能在O(n^2)运行时解决它吗？

一个常见的O(n^2) 人们对解决方案意见一致是：

public class Solution {
    int count;
    
    public int threeSumSmaller(int[] nums, int target) {
        count = 0;
        Arrays.sort(nums);
        int len = nums.length;
    
        for(int i=0; i<len-2; i++) {
            int left = i+1, right = len-1;
            while(left < right) {
                if(nums[i] + nums[left] + nums[right] < target) {
                    count += right-left;
                    left++;
                } else {
                    right--;
                }
            }
        }
        
        return count;
    }
}

--我不明白这怎么可能是O(n^2)。肯定，该算法使用一些方便的快捷方式来节省时间(主要是通过排序和使用它来实现我们的优势)，但我不明白它如何确保O(n^2)。

，这是O(n^2)而不是O(n^3)的数学原因，如果是的话，你能解释一下背后的原理吗?这样我就能再次发现它的行为了吗？

Answer 1

确定这一点的一个非常简单的方法是n^2算法，即查看循环。

外部(for)循环最多迭代n次(严格意义上说是n-2，但无论如何)。内循环取决于左和右的值。左至少为1，右边最多为len =n(技术上为len-1，但无论如何)内循环只在left < right时执行，因此在最坏的情况下，内循环最多迭代n次。

外部循环最多迭代n次。对于外部循环的每一次迭代，内环最多迭代n次。算法为O(n^2)。该算法也是O(n^3)，因为O(n^2)=O(n^3)。

另一条不是在固定时间内运行的语句是：

Arrays.sort(nums);

假设一种有效的排序算法，该操作运行在O(n^2)中的O(nlog n)中，因此不影响最终的时间复杂度。

在做时间复杂性分析时的一个技巧。忘记算法应该做什么，只看循环和它们可能运行的数量。

Answer 2

public class Solution {
    int count; //constant operation

    public int threeSumSmaller(int[] nums, int target) {
        count = 0; //constant operation
        Arrays.sort(nums); //sorting is generally considered O(nlogn)
        int len = nums.length; //constant operation

        for(int i=0; i<len-2; i++) { //O(n) operation
            int left = i+1, right = len-1; //two constant operations
            while(left < right) { //O(n) operation
                if(nums[i] + nums[left] + nums[right] < target) { //constant operation
                    count += right-left; //constant operation
                    left++; //constant operation
                } else { 
                    right--; //constant operation
                }
            }
        }
        return count; //constant operation
    }
}

上面，我用每一行的基本运行时间注释掉了您的代码块。如您所见，有两个O(n)操作和一个O(nlogn)操作。排序一般假定为O(nlogn)。您的函数每次调用一次此操作。O(n)操作是嵌套的，因此对于第一个N操作，它执行N个后续操作。这是O(n^2)。您的程序是O(nlogn) + O(n^2)，这使得它是O(n^2)总计，因为只有最高阶项才重要。