为什么这个代码是冰川
本文关键字:代码 为什么 | 更新日期: 2023-09-27 18:03:13
我本来希望这段代码执行得很快,但是对于一个有5000个元素的列表,它在我杀死它之前运行了超过20分钟。
是因为list.contains()吗?
任何想法?
public static int PNum(int N)
{
List<int> result = new List<int>();
for (int i = 1; i <= N; i++)
result.Add(i * (3 * i - 1) / 2);
int len = result.Count;
int minDiff = 10000;
int sum = 0, diff = 0;
for (int i = 0; i <= len - 1; i++)
{
for (int j = i + 1; j <= len - 1; j++)
{
diff = result[j] - result[i];
if (result.Contains(diff))
{
sum = result[i] + result[j];
if (result.Contains(sum))
{
if (diff < minDiff)
diff = minDiff;
}
}
}
}
return minDiff;
}
N
= 5000。所以,你的外部循环运行5000次迭代,内部循环运行5000次迭代,List<T>.Contains
迭代每个元素,所以它也做了5000次迭代的工作。
那么,你的循环至少要做5000次3次 = 125,000,000,000次操作,这将花费相当长的时间。
问题确实是你使用List.Contains
。使用HashSet
代替(或添加)获得O(1)个Contains
测试。