找出该算法的最坏情况运行时间，以检查一个数字是否能被 3 整除

Question

我编写了这个算法来检查数字能否被 3 整除。它的工作原理是首先检查输入 N 是否是一位数字。如果 N 不是一位数字，则计算其数字之和并将其赋给 N。外部 while 循环迭代，直到位数 n 等于 1。然后程序检查 N 的最终值是否等于0、3、6或9，在这种情况下，N可被3整除。例如，当N=5432157且n=7时，则N=5+4+3+2+1+5+7=27且n=2，那么N=2+7=9并且n=1。因此，外部 while 循环迭代 3 次。

    #include <stdio.h>
    main(){
        int N,n=0,rN,sum=0;
        printf("Enter the number: ");
        scanf("%d",&N);
        rN=N;
        while(n!=1){
            n=0;
            sum=0;
            while(N>0){
                sum+=N%10;
                N/=10;
                n++;
            }
            N=sum;
        }
        if(N==0||N==3||N==6||N==9){
            printf("\n%d is divisible by 3.",rN);
        }
        else{
            printf("\n%d is not divisible by 3.",rN);
        }
    }           

对于最坏情况的分析，我假设 N 的所有数字都等于 9。我观察到，对于位数 n 小于 11 的情况，外部 while 循环最多迭代 3 次。对于 n 大于或等于 11 但小于 10^11，循环最多迭代 4 次。我尝试了 n 大于或等于 10^11 的几种情况，发现外循环迭代了 5 次。我无法找到这种情况的通用公式。另外，对于内部 while 循环，对于外部 while 循环的每次迭代，迭代 n(N 当前值中的位数) 次，n 如何随着外部 while 循环的每次迭代而减少？

Answer 1

如果您仔细观察，您的每个（外部）迭代都会采取log(N_current)步骤。每走一步，你的数字也会变成log(N)（或者9*log(N)准确地说）。

外部迭代将继续，直到N_current有 1 位数字。

所以你的总复杂度将是 -

log(N) + log(log(N)) + log(log(log(N))) + ... + 1 ;     (1)

迭代次数将为log*N。

现在，我不知道如何减少 (1)，但如果您过度近似并将每个步骤视为log(N)，则可以将复杂度写为

O(log(N) * log*(N)) _{（注意大写O）}