C# for 循环的语法和时间复杂度的差异

Question

我试图弄清楚以下循环之间的区别是什么。

第一个是我在 codewars.com 上练习算法时编写的代码。尝试较大的测试用例时会超时。

第二个是顶级解决方案之一。它似乎在功能上相似(显然它更简洁(，但运行速度更快并且不会超时。谁能向我解释一下有什么区别？此外，第二个片段中的 return 语句让我感到困惑。此语法到底是什么意思？也许这是更有效的地方。

public static long findNb(long m)
{
int sum = 0; 
int x = new int();
for (int n = 0; sum < m; n++)
{
sum += n*n*n;
x = n;
System.Console.WriteLine(x);
}
if (sum == m)
{
return x;
}
return -1;
}

与

public static long findNb(long m) //seems similar but doesnt time out
{
long total = 1, i = 2;
for(; total < m; i++) total += i * i * i;
return total == m ? i - 1 : -1;
}

Answer 1

第二种方法使用long作为总值。您使用的m值可能足够高，足以超过int表示的值数。因此，您的数学溢出，n值变为负数。你陷入了一个无限循环，n永远不会像m那么大。

而且，就像其他人说的那样，摆脱WriteLine。

此外，第二个片段中的 return 语句让我感到困惑。此语法到底是什么意思？

它是一个三元条件运算符。

Answer 2

这两种方法大致相同，除了不需要的System.Console.WriteLine(x);破坏了乐趣：在Console上打印(UI！(是一个缓慢的操作。

如果您正在寻找一个快速的解决方案(特别是对于大m和长循环(，您可以预先计算所有(77936(值：

public class Solver {
static Dictionary<long, long> s_Sums = new Dictionary<long, long>();
private static void Build() {
long total = 0;
for (long i = 0; i <= 77936; ++i) {
total += i * i * i;
s_Sums.Add(total, i);
}
} 
static Solver() 
Build(); 
}
public static long findNb(long m) {
return s_Sums.TryGetValue(m, out long result) 
? result 
: -1;
}
}

Answer 3

当我遇到这样的微优化挑战时，我总是使用 BenchmarkDotnet。它是用于获取有关性能，内存分配，.NET Framework版本中的偏差，64位与32位等的所有见解的工具。

但正如其他人所写 - 请记住删除WriteLine((语句:)