算法技术问询：求解执行结束后p、q的值及算法时间复杂度

待分析算法 #

初始化：p = 0，q = 0，输入正整数n
循环步骤：

• 外层循环：当p < n时，执行以下操作
  1. q = q + 1
  2. 内层循环：当q < n时，执行以下操作
     • p = p + 1
     • q = q + 1
  3. 结束内层循环
• 结束外层循环

问题解答 #

1. 算法结束后变量p和q的取值 #

通过模拟不同n值的执行过程，最终结果如下：

• p的取值为n
• q的取值为n + ⌈n/2⌉（即n加上n的向上取半值）

以n=5为例的模拟过程：

• 初始状态：p=0，q=0
• 第一次外层循环（p=0 <5）：
  • q变为1
  • 内层循环（q<5）：依次执行p=1,q=2、p=2,q=3、p=3,q=4、p=4,q=5，此时q=5不满足循环条件，内层循环结束
• 第二次外层循环（p=4 <5）：
  • q变为6，内层循环条件不成立，直接结束
• 后续外层循环继续执行，直到p增加到5，此时p <n不成立，外层循环终止，最终p=5，q=8（符合5+⌈5/2⌉=8的规律）

2. 算法的时间复杂度 #

该算法的时间复杂度为O(n)。

分析：
虽然算法采用嵌套循环结构，但内层循环会快速推进p和q的取值，整体操作次数与n呈线性关系。所有循环体的总执行次数约为3n/2，属于线性时间复杂度范畴。

内容的提问来源于stack exchange，提问作者Raj Ishu