求Test(n)函数在三类输入场景下的Θ表示时间复杂度

函数基础逻辑 #

给定Test(n)函数的核心作用是查找大于1的最小正整数因数，原实现逻辑如下：

Function Test(n : Integer) : Integer
变量：
i : Integer
执行逻辑：
for i := 2 to n do
    if n mod i = 0 Return( i ) End-if
End-for
Return(n)

函数只要找到第一个能整除n的i就会立刻返回，不会执行后续循环。 #

三类场景下的最坏情况时间复杂度（Θ紧界表示） #

• n为偶数：遍历的第一个i值就是2，偶数都能被2整除，仅需要1次判断就返回，时间复杂度为Θ(1)
• n为完全平方数：完全平方数的最小正因数一定不大于√n，最坏情况为该完全平方数是素数的平方（例如n=25=5²），此时最小因数就是√n，需要遍历到i=√n才会返回，时间复杂度为Θ(√n)
• n为质数：质数不存在介于2到n-1之间的因数，必须遍历完所有2到n的取值才会返回，共执行n-1次判断，时间复杂度为Θ(n)

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