计算sqrt(1) + sqrt(2) +.+ sqrt(n)的时间复杂度是多少？

这基本上是个数学题，在“计算机科学”stackexchange上可能会更好。但是我想你可以期待程序员也知道它，而且程序员不仅仅是为了“软”的问题，所以也许它在这里是合适的。

不管怎么说。

根据目前的答案，我认为菲利普·肯德尔误解了你的问题。他认为你是在问“评估这个总和的计算复杂性是什么”。你是在问。“这一总和的增长率是多少”。

有几种方法可以用来估计级数的增长率。一个比较普遍的方法是积分法，它基本上把它变成了一个微积分问题。其思想是，取一个级数，它是根据像f(n) = n或f(n) = n^{0.5}这样的解析函数取值，它与取从1到n的(连续)范围内的“步骤”函数的积分是一样的。由于阶跃函数从上到下都有光滑函数的限制，而且光滑函数易于集成(或者至少在容易集成的情况下)，这给出了一个清晰的答案。

例如，您知道x dx的不定积分是1/2 x^2，所以和1 + 2 + ... + n是O(n^2)。

在您的例子中，您关心的是总结到sqrt(n)。sqrt(x) dx的不定积分为2/3 x^{3/2}。所以1 + sqrt(2) + ... + sqrt(n)之和是O(n^{3/2})。

然而，许多人忘记了他们的微积分。在许多情况下，您可以通过简单的启发式来估计这些事情。

例如，在sum 1 + sqrt(2) + ... + sqrt(n)中，您知道sqrt(n)是之和中最大的数字。和中有n数。所以很容易，你可以看到之和不能超过n * sqrt(n)。

现在，你希望看到的总和不能少得多。很难看出这一点，因为开头的条目很小。然而，一个典型条目的价值是什么。让我们考虑下半部分的所有数字。最后一个是sqrt(n)，中间条目是sqrt(n/2)。但是sqrt(n/2)也可以重写sqrt(n) / sqrt(2)。换句话说，序列后半段的所有条目都在一个系数sqrt(2)内，因此对于大O来说，它们是“相同的”。

具体来说，和的下半部分中的所有数字至少是sqrt(n) / sqrt(2)。还有这些数字的n/2。所以和至少是n * sqrt(n) / (2 sqrt(2))，这个函数也是O(n^{3/2})。

因此，我们知道，没有微积分，增长率是在一个常数因子的n^{3/2}。

我喜欢用这种方法来处理这个问题，因为它促进了良好的工程思维。当一个问题很难直接解决时，最好把注意力集中在典型案例上。通常情况下，如果你制作的东西效果很好--通常情况下，这在实践中是足够好的。在科学上也是如此。有时，某些公式中的确切常数很重要，你需要使用像微积分这样的强大工具来找到它。但更常见的是，人们只关心全局和微积分，而只关注封闭形式的解和精确的常数。很多时候，如果您能够理解典型的情况，这将为您提供足够的信息来解决整个问题。