c# - 时间复杂度评估？

Question

我在应用程序中实现了密码学和隐写术算法，想对这些算法进行时间复杂度评估。我不知道应该如何执行这些测试。

有没有我可以应用的测试框架或如何进行这些测试？

Answer 1

假设您没有使用递归，您应该查看您的循环。通过检查每个循环基于特定输入迭代的次数来计算是相当简单的。时间复杂度是嵌套循环运行次数的乘积。如果您有不止一组嵌套循环，将它们全部加在一起，这就是时间复杂度。例如:

for (int i=0; i<N; ++i)
{
    // Some constant time operation happens here
    for (int j=0; j<N; ++j)
    {
      // Some constant time operation happens here
    }
    // Some constant time operation happens here
} 

这个循环将在 O(N) + O(N²) = O(N + N²) = O(N²) 时间，因为循环的外部恒定时间部分在 O(N) 时间内执行，而内部部分在 O(N)*O(N) = O(N² ).

如果您使用递归，事情就更难分析了，但它归结为同一件事……计算代码的恒定时间部分被执行了多少次。建议您阅读一本关于算法分析的书(This one 几乎是该主题的标准)，这将帮助您了解如何最好地分析其他算法。