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），但找不到计算子循环的方法。那么，以上程序的时间复杂度是多少？
提前致谢。
令字符串的长度写为n。
n = str.length();
现在，外部for循环在String的整个长度上迭代，即n次。因此，外部循环复杂度为O（n）。
谈到子循环，内部while循环执行（val）^（1/62）次。因此，您可以将内部while循环复杂度视为O（log 62 val）。
所有其他语句采用恒定的时间复杂度。
因此，净时间复杂度= O（n * log 62 val）。
最后一步是因为：-
如果f1（n）= O（g1（n））并且f2（n）= O（g2（n）），则f1（n）* f2（n）= O（g1（n）* g2（n））
正如Edward Doolittle评论中提到的那样，您可以将其减少为O（n * log 2 val），因为仅可将对数基数以恒定的除数（由log 2 62）转换为基数2 。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句