了解解决方案中嵌套 while 循环的时间复杂度，以针对 C# 中的极客问题计算具有给定总和的不同对数

Question

我想检查一下我对 G4G 问题的解决方案的理解（https://www.geeksforgeeks.org/count-distinct-pairs-with-given-sum/）。问题是确定下面代码的时间复杂度，该代码计算具有特定总和的不同数字对。我不是CS专业的，但正在努力学习。

我理解 Array.Sort(arr) 本身平均需要 O(nlogn)。我想了解嵌套 while 语句的复杂性。

如果等式“arr[i] + arr[j] == K”永远不会为真，则永远不会命中内部 while 循环并且 复杂度应该是 O(n)。

但是如果相等为真，那么无论是否有重复项（这会触发内部 while 循环），i 和 j 指针都会靠近。满足相等条件导致外部 while 循环更接近它的终止条件 i < j because i,j and moved closer together.

我的猜测是，包含内部和外部 while 循环的整个块是 O(n)。我不知道我是否正确，我不确定如何证明这一点。我想要一些帮助来理解如何详细证明这个问题的时间复杂度。

// C# program to implement
// the above approach
using System;
class GFG{
 
// Function to count distinct pairs in array whose sum equal to K
static int cntDisPairs(int []arr,int N, int K)
{
     
    
    int cntPairs = 0;              // Stores count of distinct pairs whose sum equal to K
    Array.Sort(arr);              // Sort the array
    int i = 0;           // Stores index of the left pointer  
    int j = N - 1;      // Stores index of the right pointer
 
    // Calculate count of distinct pairs whose sum equal to K
    while (i < j) 
    {
        if (arr[i] + arr[j] == K)  // test if sum of current pair is equal to K
        {
            while (i < j && arr[i] == arr[i + 1])   // traverse to avoid consecutive duplicate array elements
            {
                i++; 
            }
 

            while (i < j && arr[j] == arr[j - 1])    // traverse to avoid consecutive duplicate array elements
            {
                j--; 
            }

            cntPairs += 1;      // Update cntPairs
            i++;
            j--;
        }
        else if (arr[i] + arr[j] < K)               // test if the sum of current pair less than K
        {
            i++;
        }
        else
        {
            j--; 
        }
    }
    return cntPairs;
}
 
public static void Main(String[] args)
{
    int[] arr = {0, 0, 300, 400, 50, 50, 500, 600, 700};
    int N = arr.Length;
    int K = 100;
     
    Console.WriteLine(cntDisPairs(arr, N, K));
}
}

我可以理解单个 while 循环或嵌套 while 循环对某些虚拟索引的复杂性，但我还没有看到 while 循环条件基本相同并在内部循环期间递增父循环变量的问题。

Answer 1

对于时间复杂度证明，只需注意

1. 对于每一对

   (i,j)

   ，在

   i

   或

   j

   变化之前执行一些恒定数量的操作。

2. i

   从

   0

   开始并始终递增，

   j

   从

   N-1

   开始并始终递减，在

   i = j

   循环中断。因此，在这个循环中，不超过

   N

   个不同的对

   i, j

   被分析。

因此，这意味着执行的操作总数总是小于

N

乘以某个常数，这意味着复杂度为

O(N)

.