提问人：Dmitry L. 提问时间：10/26/2021 更新时间：10/27/2021 访问量：73
在算法复杂的情况下，“#+（n） = ”是什么意思？
What does "#+(n) = " means in case of algorithms complexity?
问：
我正在读一本名为“从数学到通用编程”的书，作者是 Alexander A. Stepanov 和 Daniel E. Rose，第二章包含对埃及乘法算法的描述。其复杂性描述为 。一般来说，这是完全可以理解的，但“#+”是什么意思？它是数学函数的一种符号形式还是其他什么？#+(n) = [log n] + (ν(n) - 1)
答：
4赞
user1196549
10/26/2021
#1
“#”通常表示“的数量”，而“+”号用作索引。所以我们有“添加的数量”。
1赞
Soner from The Ottoman Empire
10/26/2021
#2
在那本书中，作者在给出方程式之前说：
multiply1 要做多少次加法？
每次调用该函数时，我们都需要在 + a 中执行 + 表示的加法。
由于我们在递归时将值减半，因此我们将调用 函数记录 n 次。有些时候，我们需要这样做 结果 + a 中的 + 表示的另一个加法。
因此，加法总数将为 #+（n）= ⌊log n⌋ + （ν（n） − 1）
int multiply1(int n, int a) {
if (n == 1) return a;
int result = multiply1(half(n), a + a);
if (odd(n)) result = result + a;
return result;
}
bool odd(int n) { return n & 0x1; }
int half(int n) { return n >> 1; }
上一个：在具有指数的数字中被忽略的小数点
评论