time-complexity - 我如何找到以 N 为单位执行 x=x+1 的次数？

Question

我也很难找到合适的 omega() 和 theta()

    x=0;
    for k=1 to n
     for j=1 to n-k
      X=X+1;

Answer 1

内部循环是 n-1 + n-2 + n-3 ... + 1 + 0。使用本教程计算算术级数的总和以找到解决方案。外部循环显然只是“n”。

这将是大θ。当您取消除第一项之外的所有内容并移除乘数时，大哦将与大θ相同，例如 Theta(2*log(n) + 5) 变为 O(log(n))。Omega 在这种情况下与 big-Oh 相同，因为最好的情况和最坏的情况是相同的；或者你可以欺骗说大欧米茄是常数时间，因为每个函数的大欧米茄都是常数时间。

Answer 2

首先，看看你的界限。k=1 和 k=n。

对于 k=1，内部循环执行 (n-1) 次。对于 k=n，内部循环执行 (0) 次。

因此，0 + 1 + ... + (n-1) 是算术和 => (n-1)(n)/2 次。

现在，在几个小值上测试它:)

Answer 3

答案是这样的：n-1 + n -2 + n -3 + ... = n*n - (1+2+3+ ... + n) = n^2 - n(n-1) /2