我在Cormen 等人的《算法导论》第 47 页看到了这段话。：
表达式中匿名函数的数量被理解为等于渐近符号出现的次数。例如在表达式中：
Σ ( i =1 到n ) O( i )
只有一个匿名函数（i的函数）。此表达式与 O(1) + O(2) + ... + O( n ) 不同，后者实际上并没有清晰的解释。
这是什么意思？
问问题
701 次
2 回答
6
I think they're saying that when they use that notation (sum of a big-O), it means there's a single O(i) function (call it f(i)), and then the expression refers to the sum from 1 to n of that function.
This isn't the same thing as if there were n different functions (call them f_1(i) to f_n(i)), each of which is O(i), and then the expression refers to the sum of f_1(1) + f_2(2) + ... + f_n(n). That latter thing is not what the notation means.
于 2012-10-01T00:33:26.177 回答
0
我认为您首先应该理解“表达式中匿名函数的数量被理解为等于渐近符号出现的次数”。这意味着如果
Σ (i=1 to n) O(i)
所以匿名函数等于 O(i) 例如Σ (i=1 to n) f1(i)
如果Σ (i=1 to n) O(i)+O(i)
匿名函数应该有两个等于 O(i)+O(i) 的函数，例如Σ (i=1 to n) f1(i)+f2(i)
于 2014-07-02T03:45:32.557 回答