我很新手,不太懂如何计算算法或代码的时间复杂度,所以我不确定这个函数的复杂度是什么:
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
循环将遍历每个数字,所以对于一个4位数,如1221
,将有4个动作需要完成(每个动作需要一些执行时间),因此如果我的数字相对于其数字变为2倍,则例如12222221
,则我需要完成8个动作。然后,我的输入增加了2倍,时间也增加了2倍,因此时间复杂度应为O(n)
。这正确吗?
O(floor(log10(n)) + 1)
是数字计数函数:我们取该数字的log10
(即找到使得 $10^x=n$ 的 x 值)-例如log10(10) = 1
,log10(100) = 2
,log10(1) = 1
,log10(7) = 0.845...
。然后我们向下取整,因为例如 14 (log10(14)=1.146
) 和 11 (log10(11)=1.041
) 中的数字位数相同。正如您所看到的,数字计数向下偏移了 1,因为我们是相对于 10 进行测量的。因此,我们在上面加上一个 1 来获取数字计数。由于它是一个 O(digits) 循环,我们只需将floor(log10(n))+1
插入其中以获取相对于输入数字的最终大 O。 - Geza Kerecsenyi