算法循环问题求助：输出结果、时间复杂度分析及代码调试

嘿，看起来你在实现这个算法的时候把循环结构搞混了，先帮你梳理代码问题，再一步步解答你的疑问～

一、你的代码问题修正 #

你的代码存在几个关键问题：

• 错误地把两个需要顺序执行的循环写成了嵌套结构，原算法是先执行完第一个循环再执行第二个，不是嵌套
• 语法错误：i=>1应该写成i >= 1（箭头方向反了）
• 输出语句的位置不对，且代码未完成

修正后的正确代码如下：

public class HelloWorld1 {
    public static void main(String[] args) {
        int n = 2; // 可以替换成4来测试不同情况
        // 第一个循环：从1到1.5n，依次打印i
        for (int i = 1; i <= 1.5 * n; i++) {
            System.out.println(i);
        }
        // 第二个循环：从n到1倒序打印i
        for (int i = n; i >= 1; i--) {
            System.out.println(i);
        }
    }
}

二、问题(a)：n=2和n=4时的输出 #

当n=2时： #

1. 第一个循环：1.5*2=3，i从1遍历到3，输出内容为：1、2、3
2. 第二个循环：i从2倒序到1，输出内容为：2、1

完整输出顺序：

1
2
3
2
1

当n=4时： #

1. 第一个循环：1.5*4=6，i从1遍历到6，输出内容为：1、2、3、4、5、6
2. 第二个循环：i从4倒序到1，输出内容为：4、3、2、1

完整输出顺序：

1
2
3
4
5
6
4
3
2
1

三、问题(b)：时间复杂度分析 #

时间复杂度关注的是总执行操作数的量级：

• 第一个循环的执行次数是 $\lfloor1.5n\rfloor$ 次（i为整数，若1.5n是小数则向下取整），量级为 $O(n)$
• 第二个循环的执行次数是n次，量级也为 $O(n)$
• 总操作次数为 $1.5n + n = 2.5n$，忽略常数系数后，时间复杂度为 $O(n)$

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