algorithm - 计算时间复杂度时的“要考虑的操作”(例如，如果返回，则分配..)

我在研究算法时间复杂度和递归性。
实际上我对解决递归很在行，因为这是简单的数学。但代码部分是问题所在。
例如，这就是我带来的问题：
https://brilliant.org/practice/big-o-notation/?problem=complexityrun-time-analysis-2-2

public int P(int x , int n){
    if (n == 0){
        return 1;
    }
    if (n % 2 == 1){
        int y = P(x, (n - 1) / 2);
        return x * y * y;
    }
    else{
        int y = P(x, n / 2);
        return y * y;
    }
}

它是一个简单的幂函数t（n）=o（g（n））是这个函数的运行时间，我必须找到它。
解决方案是，
“当幂为奇数时，执行额外的乘法运算。为了计算时间复杂度，让我们先看看最坏的情况，这意味着我们假设需要一个额外的乘法运算。
但是，我不明白下一部分，解决方案是：
递归关系是

T(n) = T(n/2) + 3, T(1)=1

1）为什么常数是第3部分？

if (n % 2 == 1){
        int y = P(x, (n - 1) / 2);
        return x * y * y;
    }

2）我实际上也不明白为什么t（1）=1。
我很困惑。在计算时间复杂度时，我们应该考虑哪些操作？
例如，t（1）=1部分必须与

if (n == 0){
        return 1;
    }
if (n % 2 == 1){
        int y = P(x, (n - 1) / 2);
        return x * y * y;
    }

这一部分，我想问t（1）=1是否来自if语句/assign语句/return语句。
我后来理解了，解决了上面的递归关系，但我仍然坚持递归关系本身。
请帮助我阿尔戈古鲁。

最佳答案

在计算时间复杂度时，我们应该考虑哪些操作？
答案会让你有点失望：不管你算什么手术这就是为什么我们在分析算法和表达它们的时间/内存需求时使用big-oh。这是一个渐近表示法，它描述了大数值n的算法发生了什么。根据大oh的定义，我们可以说1/2n^2和10n^2+6n+100都是o（n^2），即使它们不是同一个函数。计算所有的操作，只会增加一些常数因子，这就是为什么你计算哪些操作并不重要。
由上可知，常数仅为o（1）。例如，这忽略了细节，因为10和10000都是o（1）。
有人可能会说，在表达式T(n) = T(n/2) + 3中指定确切的操作数是不太正确的，因为没有定义操作是什么，而且同一个操作在不同的计算机上可能花费不同的时间，所以精确计算操作数充其量有点毫无意义，在最糟糕的。更好的说法是T(n) = T(n/2) + O(1)。
T(1)=1表示在恒定时间内求解的基本情况（读取：每次的操作数恒定）同样，一种更好（更正式）的说法是T(1)=O(1)。

关于algorithm - 计算时间复杂度时的“要考虑的操作”(例如，如果返回，则分配..)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/49142941/