咱们一步步拆解这个算法的时间复杂度推导哈，结合你给出的n=100的例子来理清楚：

• 先明确循环结构（基于你的观察）
  根据你描述的执行逻辑，算法的循环嵌套大概是这样的：

  for (i = 1; i <= sqrt(n); i += 2) {
      for (j = ...; j <= log₃(n/2); ...) {  // 执行log₃(n/2)次迭代
          for (k = i; k <= sqrt(n); k++) {  // 执行次数随i变化
              // 核心操作
          }
      }
  }
  

• 步骤1：统计外层i循环的迭代次数
  i从1开始，每次步长为2，直到不超过sqrt(n)。比如n=100时，i取1、3、5、7、9，共5次。整体来看，迭代次数约为sqrt(n)/2，忽略常数系数后，这部分的复杂度是O(sqrt(n))。

• 步骤2：计算所有k循环的总执行次数
  每个i对应的k循环次数是sqrt(n) - i + 1，把这些次数加起来是一个等差数列：

  • 首项（i=1时）：sqrt(n)
  • 末项（最后一个i时）：2（比如n=100时，最后i=9，k执行2次）
  • 项数：就是i循环的迭代次数，约sqrt(n)/2

  用等差数列求和公式计算总和：

  总和 ≈ (sqrt(n) + 2) × (sqrt(n)/2) / 2 = (n + 2sqrt(n))/4
  

  这里n是主导项，低阶项sqrt(n)和常数系数可以忽略，所以这部分的复杂度是O(n)。

• 步骤3：加上j循环的影响
  每个k循环的执行都会伴随j循环的log₃(n/2)次迭代。对数的底数不影响复杂度的阶数，所以log₃(n/2)可以简化为O(log n)。

• 最终总时间复杂度
  把各部分结合起来，总执行次数是O(n) × O(log n) = O(n log n)。

  验证一下你的例子：n=100时，k循环总次数是30，log₃(50)≈3.56，总操作次数约107——这和n log n的数值差异来自常数系数和低阶项，但复杂度的核心阶数依然是O(n log n)。

内容的提问来源于stack exchange，提问作者Akrabul Islam Imran