我怎样才能找到这个算法的时间复杂度？
How can I find the temporal complexity of this algorithm?
fun xpto(n: Int, m: Int): Int {
return if (n / m == 0) 0 else 1 + xpto(n / m, m)
}
m如何影响时间复杂度？我的第一个想法是 O(n)，但我不确定。
此函数将第一个参数除以第二个，并再次使用该商作为下一次调用的第一个参数，只要该商不为零即可。对于正整数，递归调用的次数因此等于
的最大幂
/ >= 1，或
>=
因此递归调用的次数是
= ⌊log⌋
这也是函数将 return 的值，因为每次递归调用都会将 1 添加到递归返回的结果中。
时间复杂度
假设我们可以将除法视为常数时间操作，那么我们的时间复杂度为 O(log)。的值（即对数的底数）与大 O 表示法无关，因为它提供了 upper bound。请注意对于给定值 ，增加（绝对）值 不会增加 花在算法上的时间。
但是，有很大的类别，我们可以在其中降低渐近上限。例如，在 < 的类别中，复杂度为 O(1)。对于其他类别，它可以是 O(1) 和 O(log) 之间的任何其他值。因此，对于所有类别，我们将 O(log) 作为上限。
以下所有时间复杂度表达式都适用于该算法：
渐近上限：O(log)
渐近下界：Ω(1)
渐近紧界：ϴ(log)
负输入
参数的符号没有影响，因为递归调用的次数只取决于两个参数的绝对值。
如果至少有一个参数为负，我们还必须假设整数除法（在实际的编程语言中）会将 舍入为零，否则算法可能会进入无限递归，总是产生 -1 的商。
限制
- 应该是非零的，否则会出现被零除的异常。
- abs() 不应该为 1，因为当它非零时会导致无限递归。有关相关讨论，请参阅 log base 1 of 1。
fun xpto(n: Int, m: Int): Int {
return if (n / m == 0) 0 else 1 + xpto(n / m, m)
}
m如何影响时间复杂度？我的第一个想法是 O(n)，但我不确定。
此函数将第一个参数除以第二个，并再次使用该商作为下一次调用的第一个参数，只要该商不为零即可。对于正整数，递归调用的次数因此等于
的最大幂/ >= 1，或
>=
因此递归调用的次数是
= ⌊log⌋
这也是函数将 return 的值，因为每次递归调用都会将 1 添加到递归返回的结果中。
时间复杂度
假设我们可以将除法视为常数时间操作，那么我们的时间复杂度为 O(log)。的值（即对数的底数）与大 O 表示法无关，因为它提供了 upper bound。请注意对于给定值 ，增加（绝对）值 不会增加 花在算法上的时间。
但是，有很大的类别，我们可以在其中降低渐近上限。例如，在 < 的类别中，复杂度为 O(1)。对于其他类别，它可以是 O(1) 和 O(log) 之间的任何其他值。因此，对于所有类别，我们将 O(log) 作为上限。
以下所有时间复杂度表达式都适用于该算法：
渐近上限：O(log)
渐近下界：Ω(1)
渐近紧界：ϴ(log)
负输入
参数的符号没有影响，因为递归调用的次数只取决于两个参数的绝对值。
如果至少有一个参数为负，我们还必须假设整数除法（在实际的编程语言中）会将 舍入为零，否则算法可能会进入无限递归，总是产生 -1 的商。
限制
- 应该是非零的，否则会出现被零除的异常。
- abs() 不应该为 1，因为当它非零时会导致无限递归。有关相关讨论，请参阅 log base 1 of 1。