algorithm - 这个函数的正确时间复杂度是多少

Question

我是数据结构和算法的初学者。我在一本书(Data Structures And Algorithms Made Easy In Java)中遇到过这个问题，书中给出的复杂度为 O(√n)。根据我的理解，随着输入的增长，函数看起来大于 O(√n) 但小于 O(n)。

public void function (int n) {
   int i=1, s=1;
   // s is increasing not at rate 1 but i
   while( s <= n) {
      i++;
      s= s+i;
      System.out.println(“*");
   }
}

你能解释一下这个函数的正确时间复杂度是多少吗？

Answer 1

书是对的。每次，one添加到 i和 i添加到 s .因此，s将是 1和 1 + 2 , 1 + 2‌ + 3 , ..., 1 + 2 + 3 + ... + k .现在，k是运行循环次数，复杂度为Theta(k)或 O(k) .现在找到k的值，我们需要解决1 + 2 + ... + k = n .如 1 + 2 + ... + k = k(k+1)/2 ，我们将有 k*(k+1)/2 = n .因此，k = Theta(sqrt(n)) (只需解方程)，这意味着算法在O(sqrt(n)) .