在 Big-O 术语中，如果 O(n-1) 与 O(n) 相同，那么为什么在主定理中 T(n-1) 不等于 T(n)？
In Big-O terms if O(n-1) is the same thing as O(n) then why in the master theorem is T(n-1) not equal T(n)?
好的，所以我对 CS 很陌生，最近学习了 Big-O、Theta 和 Omega 以及主定理，在讲座中我看到出于某种原因情况并非如此，我想知道这是为什么？
虽然O(n)和T(n)都在外面使用大写字母，中间使用小写n，但它们代表的概念根本不同。
如果您使用递归关系分析算法，通常让 T(n) 表示算法完成大小为 n 的输入所需的时间。因此，我们不会期望 T(n) 与 T(n-1) 相同，因为在大多数情况下，当您为算法提供更大的输入时，算法需要更长的时间才能达到 运行。
更一般地说，对于任何函数f，如果你想声明f(n) = f(n-1)，你需要解释为什么你可以假设是这样，因为通常情况并非如此。
这里的棘手之处在于，当我们编写 O(n) 时，看起来我们正在编写一个名为 O 并传入参数 n 的函数，但表示法意味着完全不同的东西。符号 O(n) 是“某些函数的占位符，当输入变得非常大时，它从上方以 n 的倍数为界”。类似地，O(n-1) 表示“某个函数，当输入变得非常大时，从上方以 n-1 的倍数为界。”碰巧的是，任何以 n 的倍数为界的函数也以 n-1 的倍数为界，这就是为什么 O(n) 和 O(n-1) 表示同一事物的原因。
希望对您有所帮助！
好的，所以我对 CS 很陌生，最近学习了 Big-O、Theta 和 Omega 以及主定理，在讲座中我看到出于某种原因情况并非如此，我想知道这是为什么？
虽然O(n)和T(n)都在外面使用大写字母，中间使用小写n，但它们代表的概念根本不同。
如果您使用递归关系分析算法，通常让 T(n) 表示算法完成大小为 n 的输入所需的时间。因此，我们不会期望 T(n) 与 T(n-1) 相同，因为在大多数情况下，当您为算法提供更大的输入时，算法需要更长的时间才能达到 运行。
更一般地说，对于任何函数f，如果你想声明f(n) = f(n-1)，你需要解释为什么你可以假设是这样，因为通常情况并非如此。
这里的棘手之处在于，当我们编写 O(n) 时，看起来我们正在编写一个名为 O 并传入参数 n 的函数，但表示法意味着完全不同的东西。符号 O(n) 是“某些函数的占位符，当输入变得非常大时，它从上方以 n 的倍数为界”。类似地，O(n-1) 表示“某个函数，当输入变得非常大时，从上方以 n-1 的倍数为界。”碰巧的是，任何以 n 的倍数为界的函数也以 n-1 的倍数为界，这就是为什么 O(n) 和 O(n-1) 表示同一事物的原因。
希望对您有所帮助！