好吧，我对 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) 表示相同的东西。
希望这有帮助!
关于math - 在 Big-O 术语中，如果 O(n-1) 与 O(n) 相同，那么为什么在主定理中 T(n-1) 不等于 T(n)？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/62630597/