假设我有以下算法：
for(int i = 1; i < N; i *= 3) {
sum++
}
我需要使用波浪符号计算复杂度，这基本上意味着我必须找到一个波浪函数，以便当我将算法的复杂度除以这个波浪函数时，无穷大的限制必须为 1。
我认为没有必要计算确切的复杂度，我们可以忽略常量，然后我们就有了波浪线复杂度。
通过查看索引的增长，我假设这个算法是
~ log N
但是，在这种情况下，基数不是二进制对数函数，而是 3。这对确切的符号有影响吗？增长的顺序是否完全相同，因此我们可以在使用波浪符号时忽略基数吗？我是否正确处理这个问题？
您是对的，for 循环执行ceil(log_3 N)次数，其中log_3 N表示 的以 3 为底的对数N。
不，使用波浪符号时不能忽略基数。
这是我们如何推导出时间复杂度的方法。我们将假设 for 循环的每次迭代都花费C一些常数C>0。
表示T(N)for 循环的执行次数。由于在j第 - 次迭代时 的值为i，3^j因此我们进行的迭代次数是最小j的3^j >= N。取两边的以 3 为底的对数，我们得到j >= log_3 N。因为j是整数，j = ceil(log_3 N). 因此T(N) ~ ceil(log_3 N)。
让S(N)表示 for 循环的时间复杂度。因此，“总”时间复杂度为C * T(N)，因为每次T(N)迭代的成本为C，在波浪符号中我们可以写为S(N) ~ C * ceil*(log_3 N)。