在GeeksforGeeks平台上给出不同运行时间的两个等效代码

Question

我在GeeksforGeeks上解决了一个问题，关于从一个大小为n的未排序数组arr[]中，使用三个不同的数组元素作为三角形的边，找到可能的三角形总数。这是上述问题的第一次实现。…

int findNumberOfTriangles(int arr[], int n)
{
// code here
sort(arr,arr+n);

int i,j,k,count=0;

for(i=0;i<n-2;i++)//first side of triangle
{
k=i+2; // third side of triangle , ie. rightmost element initialized
for(j=i+1;j<n;j++)    //second side of triangle
{    
// search for all elements less than sum of the 
// first and second side of the triangle
while(k<n)
{
if(arr[i]+arr[j]>arr[k]) 
k++;                
}

count=count+ k-j-1; //adds no of triangle possible for each pair of sides
}
}

return count;
}

上述实现是正确的，并且应该具有O(N^2(时间复杂性。对于上述代码，我正在从GeeksforGeeks平台获取TLE(超过时间限制(，预期时间限制=1.02秒。

现在将下面的实现与上面的实现进行比较。

int findNumberOfTriangles(int arr[], int n)
{
// code here
sort(arr,arr+n);

int i,j,k,count=0;

for(i=0;i<n-2;i++)//first side of triangle
{
k=i+2; // third side of triangle , ie. rightmost element initialized
for(j=i+1;j<n;j++)    //second side of triangle
{    
// search for all elements less than sum of the 
// first and second side of the triangle
while(k<n && arr[i]+arr[j]>arr[k])
k++; 

count=count+ k-j-1; //adds no of triangle possible for each pair of sides
}
}

return count;
}

实现的不同之处仅在于循环的第二个内的while循环f条件从wheel body内部移动到条件声明部分。其时间复杂性与第一个实现相同：O(N^2(。

但是，GeeksforGeeks接受了该实现，所用时间=(0/1.0(。

有人能告诉我为什么两个等价的代码之间有这么大的性能差异吗。这是由于GeeksforGeeks平台还是由于C++语言的特性。GeeksforGeeks使用g++5.4编译器

链接：https://practice.geeksforgeeks.org/problems/count-possible-triangles-1587115620/1

Answer 1

它们不等价。

while(k<n)
{
if(arr[i]+arr[j]>arr[k]) 
k++;                
}

对于遇到的第一个if条件为false的元素，此循环将永远继续循环，因为k不会递增。

这个：

while(k<n && arr[i]+arr[j]>arr[k])
k++; 

当k<n或在arr[i]+arr[j]>arr[k]为false的第一个元素上时停止循环。

考虑这个例子

k            arr[i]+arr[j]>arr[k]
1            true
2            true 
3            false 
...           false
n

这首先计数到k = 2，然后从不停止，因为k不再递增。第二个循环直到k = 2，并在k = 3时停止。

附言：(免责声明——我会告诉你我的个人观点，尽管事实确实如此(Geeksfforgeks是一个很好的地方，可以找到糟糕的教程、有问题的代码，这些代码通常是非标准的，但声称对初学者有好处(事实并非如此(，以及误导性的、经常错误的解释。错误也可能发生在这里，但通常情况下，有人的评论和回答可以被纠正(或者当他们错得太离谱时被否决(。如果你想学习C++，我建议你这样做：最终C++图书指南和列表