时间复杂度：

定义：在计算机科学中，算法的时间复杂度是一个函数，定量描述了算法的运行时间。算法中基本操作的执行次数，即算法的时间复杂度。（基本操作：指算法中最频繁执行且耗时相对固定的操作）

大O表示法(Big O notation)：

1、用1取代所有加法常数

2、只保留最高阶项

3、去除该项的乘法常数这个过程得到的结果称为“大O阶”，目的在于去掉影响较小的项，通常用字母N来表示输入规模。

1、$O(1)$：常数复杂度

如果循环次数是常数（即与输入无关），无论这个常数是 10 还是 1,000,000，时间复杂度都被认为是 O(1)。实际运行时间会随常数变大，但复杂度分析中忽略常数因子 例如：以下样例

// 时间复杂度：O(1)
// 判断依据：操作次数固定，与输入数据无关。
// 示例：即使循环执行多次，只要次数不随输入变化，就属于常数时间。
for (int i = 1; i <= 1000000; i++) {
    // 固定循环次数，时间复杂度仍是 O(1)
    // 只关注增长趋势，不考虑具体运行时间
}

2、$O(n)$：线性复杂度

// 时间复杂度：O(n)
// 判断依据：循环次数与输入 n 成正比，每次操作都执行一次。
// 示例：n 越大，运行次数越多。
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
    // 每次循环执行一次，总共执行 n 次
}

3、$O(n^2)$:平方复杂度

// 时间复杂度：O(n²)
// 判断依据：嵌套两层循环，每层都与 n 有关，总次数为 n × n。
// 示例：外层 n 次 × 内层 n 次 = n² 次。
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
        // 总共执行 n² 次
    }
}

4、$O(log n)$：对数复杂度

// 时间复杂度：O(log n)
// 判断依据：每次操作将问题规模缩小一半。
// 示例：除以 2 处理。
int n;
while (n > 1) {
    n /= 2;
    // 每次处理一半，总共 log₂(n) 次
}

5、$O(m + n)$ 的时间复杂度

int m, n;
cin >> m >> n;

// 第一个循环与 m 有关
for (int i = 0; i < m; i++) {
    // 执行 m 次
}

// 第二个循环与 n 有关
for (int j = 0; j < n; j++) {
    // 执行 n 次
}

1、{{ select(1) }}大O表示法的主要目的是：

• 计算算法的精确运行时间
• 描述算法在最坏情况下的增长趋势
• 比较不同编程语言的效率
• 测量算法的内存使用情况

2、{{ select(2) }}在时间复杂度分析中，我们通常关注：

• 算法的实际运行时间（以秒为单位）
• 输入规模趋近无穷大时的增长趋势
• 算法在特定硬件上的性能
• 代码的行数

3、这段代码的时间复杂度是？

int n = 100;
cin >> n;
for (int i = 0; i < n; i *= 2) {
    cout << i << endl;
}

{{ select(3) }}

• $O(n)$
• $O(log n)$
• $O(n log n)$
• $O(0)$

4、下列代码的时间复杂度为？

int n = 100;
cin >> n;
for (int i = 0; i < n; i++) {
    for (int j = i; j < n; j++) {
        cout << i + j << endl;
    }
}

{{ select(4) }}

• $O(n)$
• $O(n log n)$
• $O(n²)$
• $O(1)$

5、这段代码的时间复杂度是？

int n;
cin >> n;
for (int i = 0; i < n; i++) {
    for (int j = 0; j < 10; j++) {
        cout << i * j << endl;
    }
}

{{ select(5) }}

• $O(n)$
• $O(n²)$
• $O(1)$
• $O(n log n)$

6、{{ select(6) }}时间复杂度O(1)表示：

• 算法运行时间与输入大小无关
• 算法运行时间最短
• 算法只执行一次操作
• 算法运行时间固定为1秒

7、{{ select(7) }}在时间复杂度分析中，我们通常忽略：

• 最高阶项
• 常数因子和低阶项
• 输入规模
• 循环结构

8、下列代码的时间复杂度是多少？

for (int i = 0; i < 100; i++) {
    cout << i << endl;
}

{{ select(8) }}

• $O(n)$
• $O(1)$
• $O(n²)$
• $O(log n)$

9、以下代码的时间复杂度为？

int n;
cin >> n;
while (n > 0) {
    n = n / 2;
}

{{ select(9) }}

• $O(n)$
• $O(1)$
• $O(log n)$
• $O(n log n)$

10、分析这段代码的时间复杂度：

int m,n;
cin >> n >> m;
for (int i = 0; i < m; i++) {
    cout << i << endl;
}
for (int j = 0; j < n; j++) {
    cout << j << endl;
}

{{ select(10) }}

• $O(m + n)$
• $O(m × n)$
• $O(m)$
• $O(n)$