algorithm - “Operations to consider” (ex. If, return, assign..) 计算时间复杂度时

Question

我正在研究算法 - 时间复杂度和递归。我实际上可以解决递归问题，因为它是简单的数学。但是代码部分是问题所在。

例如，这是我带来的问题: 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语句..

后来我明白了，解决了上面的递归关系，但是我卡在了递归关系本身。

请帮助我算法专家s..

Answer 1

which operations should we consider while calculating time complexity?

答案会让您有点失望:算什么操作并不重要。这就是为什么我们使用 big-Oh 来分析算法和表达它们的时间/内存需求。它是一种渐近符号，描述了当 n 值很大时算法会发生什么。根据 Big-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)。