依赖for循环的时间复杂度

Question

string str = "abcdefghijklmnopqrstuvwxyz";
int sum = 0;
for(int i=0; i<str.length; i++)
{
    int val = str[i];
    while(val > 0)
    {
       sum = val % 62;
       val = val / 62;
    }
}

我知道父循环执行n+1次，子循环执行(val)^(1/62)次。对于父循环，时间复杂度将为 O(n)，但找不到计算子循环的方法。那么，上述程序的时间复杂度是多少？

提前致谢。

Answer 1

让字符串的长度写成n。

n = str.length();

现在，外部 for 循环遍历字符串的整个长度，即 n 次。因此，外部 for 循环复杂度为 O(n)。

关于子循环，内部 while 循环执行 (val)^(1/62) 次。因此，您可以将内部 while 循环复杂度视为 O(log₆₂ val).

所有其他语句都采用常数时间复杂度。

因此，净时间复杂度= O(n * log₆₂ val).

最后一步是因为：-

If f1(n) = O(g1(n)) and f2(n) = O(g2(n)),then f1(n) * f2(n) = O(g1(n) * g2(n))

如评论中 Edward Doolittle 所述，您可以将其减少到 O(n * log₂ val)因为对数基数只能通过常数除法（按 log₂62）转换为基数 2。