前言

算法是程序的灵魂，而程序则是由数据结构与算法共同构成的。数据结构与算法既有联系又有区别，理解它们的关系对于掌握算法设计与分析至关重要。

一、时间复杂度分析

1.1 算法的时间复杂度概述

算法的效率主要取决于问题规模。我们通常通过分析算法的渐进上界来确定其时间复杂度，常见的时间复杂度包括常数阶、线性阶、平方阶、对数阶、n log n 阶、立方阶和指数阶等。需要注意的是，低阶项通常可以忽略不计，例如 O(n² + n) 可以简化为 O(n²)。

1.2 时间复杂度示例

从上至下，时间复杂度依次递增。每当遇到一个时间复杂度较高的算法时，应尽量寻求优化方法。

简称	执行次数	时间复杂度
常数阶	6	O(1)
线性阶	6n + 6	O(n)
平方阶	6n² + 6n + 6	O(n²)
对数阶	6log₂n + 6	O(log n)
n log n 阶	6n log₂n + 6	O(n log n)
立方阶	6n³ + 6n² + 6n + 6	O(n³)
指数阶	2ⁿ + 6	O(2ⁿ)

2.1 等差数列

等差数列的通项公式为：

aₙ = a₁ + (n - 1)d（d ≠ 0）

前n项和为：

Sₙ = n/2 [2a₁ + (n - 1)d] = n(a₁ + aₙ)/2

2.2 等比数列

等比数列的通项公式为：

aₙ = a₁ qⁿ⁻¹（q ≠ 0）

前n项和为：

当 q ≠ 1 时，Sₙ = a₁ (1 - qⁿ) / (1 - q)

当 q = 1 时，Sₙ = n a₁

2.3 常见数列的前n项和

通过公式与实例结合练习，理解各类数列的求和方法。

（此处可插入数列求和的练习题或示例）

2.4 数列类型的时间复杂度推导

程序代码：

#include 
   
    using namespace std;void solve() {    int sum = 0;    for (int i = 0; i < n; ++i) {        sum += i;    }}

时间复杂度分析：

通过分析循环体的执行次数，可得时间复杂度为 O(n³)。详细推导过程可参考附图。

3.1 递推式计算：递归算法的分析

程序代码：

#include 
   
    #include 
    
     using namespace std;void mergesort(vector
     
       &before) {    if (before.size() == 1) return before;        vector
      
        left, right;    for (int i = 0; i < before.size() / 2; ++i) {        left.push_back(before[i]);    }    for (int i = before.size() / 2; i < before.size(); ++i) {        right.push_back(before[i]);    }        left = mergesort(left);    right = mergesort(right);        vector
       
         add_left_right;    int i = 0, j = 0;    while (i < left.size() && j < right.size()) {        if (left[i] < right[j]) {            add_left_right.push_back(left[i]);            ++i;        } else {            add_left_right.push_back(right[j]);            ++j;        }    }        if (i == left.size()) {        for (int k = j; k < right.size(); ++k) {            add_left_right.push_back(right[k]);        }    } else if (j == right.size()) {        for (int k = i; k < left.size(); ++k) {            add_left_right.push_back(left[k]);        }    }        return add_left_right;}void solve() {    int n;    vector
        
          my_array; while (cin >> n) { my_array.push_back(n); } my_array = mergesort(my_array); for (auto iter : my_array) { cout << iter << " "; } cout << endl;}int main() { solve(); return 0;}