检查数字是否为 armsgstrong 数字的时间复杂度

Question

我正在与一位朋友讨论检查一个数字是否为阿姆斯壮数字的算法的运行时成本。仅供那些不知道什么是阿姆斯特朗数的人：

A number is an Armstrong Number or narcissistic number if it is equal to the sum of its own digits raised to the power of the number of digits.

这是我编写的用于检查该号码是否为 Armstrong 号码的例程：

bool check_armstrong_number(int num){

   int number_copy = num; // Store the number in another variable to compare afterwards
   int digits = 0; // Stores the number of digits in the number.

   // Calculate the number of digits in the number
   while(number_copy){
    number_copy = number_copy/10;
    digits++;
   }

   number_copy = num;

   int sum = 0;  // To construct numbers from sum of digits raise to the power number_of_digits.
   while(num){
       int unit_digit = num % 10; // Get the unit digit with the help of modulus operator.
       sum  = sum + std::pow(unit_digit,digits);  // Calculate unit_digit^digits
       num = num / 10;
    }
    return (sum == number_copy); // Returns true only if sum equals original number
  }

我朋友说算法是 O(log N) ，而我认为是 O(log^2(N))。我认为对数字的迭代是 O(log N) 操作（因为整数中的位数是 log N 的顺序），并且每个计算的 std::pow(unit_digit,digits) 也在 O(log N) 左右。因此，O(log N) log N 计算的计算时间应该在 O(log^ 2N)。谁能澄清一下？

Answer 1

这是 O(log(n)*log(log(n)) 。
迭代 .
的 Log(n) 在 pow(a,b) 中，复杂度为 log(b) 。所以这里你的 b = log(n) .
所以 log(log(n)) 对于 pow 函数 .

检查数字是否为 armsgstrong 数字的时间复杂度

Time Complexity to check if a number is an armsgstrong number or not

language-agnostic

algorithm

time-complexity