我对计算算法或代码的时间复杂度还很陌生，所以我不确定下一个函数的复杂度是多少:

isPalindrome <- function(num){
  if(num < 0) return(F)
  rev <- 0
  orig_num <- num
  while(num != 0){
    pop <- num %% 10
    num <- num %/% 10
    rev <- rev*10 + pop
  }
  if(orig_num == rev) return(T)
  else return(F)
}

然后调用函数，例如isPalindrome(122221) 将返回 TRUE。 基本思想是计算一个反向数，然后与原始数进行比较，如果它们相等则为回文。

我的基本直觉是，为了计算反向数字，while 循环将遍历每个数字，因此例如对于像 1221 这样的 4 位数字，将会有要执行 4 个操作(每个操作都需要一些执行时间)，因此如果我的数字相对于它的数字变大 2 倍，例如 12222221 那么我将需要执行 8 个操作。然后，我的输入增加了 2，时间也增加了 2，所以时间复杂度应该是 O(n)。这是正确的吗？

最佳答案

您的直觉是正确的:您的算法将在 O(n) 中运行关于数字的数字。也就是说，和数字的大小比较，一个O(floor(log10(n)) + 1)，这就是数数函数。

https://stackoverflow.com/questions/57447747/