c - 找出该算法的最坏情况运行时间，以检查一个数字是否能被 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)}