数据结构(一) 绪论

一. 时间复杂度:

        (1)定义:

               时间复杂度是衡量算法执行时间随输入规模(通常用n表示)增长的变化趋势的指标,时间复杂度用O符号表示

                用于描述算法在最坏情况下或平均情况下的时间需求

                时间复杂度关注的是操作次数的增长率，而非具体执行时间

        常见的时间复杂度由小到大依次为:

                O(1) < O(log2n) < O(n) < O(nlog2n) < O(n²) < O(n³) < ...... < O(2^n) < O(n!)

        Example:

                1.若一个算法需要执行 3n² + 2n + 1 次操作，其时间复杂度为O(n²)，因为最高阶项n²主导增长趋势，常数系数和低阶项容易被忽略

                2. O(1): 访问数组中的某个元素

                3. O(n): 遍历数组求和

int Sum_Array(int num[]){
    int sum=0;
    for(int i=0; i<N; i++){
        sum += num[i];
    }
    return sum;
}

        输入规模为n, for循环执行n次，时间复杂度为O(n)

                4.O(n²) : 冒泡排序

void bubbleSort(int arr[], int n){
    for(int i=0;i<n-1;i++){
        for(int j=0;j<n-i-1;j++){
            if(arr[j]>arr[j+1]){
                int temp=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=temp;
            }
        }
    }
}

        for循环执行次数为n(n-1)/2，时间复杂度为O(n²)                   

        (2)如何判断时间复杂度:

                1.逐层分析代码:

                        单层循环 -> O(n)

                        双层循环 -> O(n²)

                        分治算法(归并排序) -> O(nlogn)

                2.注意循环终止条件:

                        若循环变量每次乘以2（如 i *= 2），循环次数为 O(log⁡n)

                3.递归：

                        递归调用次数和输入规模有关，斐波那契数列递归的时间复杂度为O(2^n)

二. 空间复杂度:

        (1)定义：

                空间复杂度衡量算法运行过程中临时占用的存储空间大小，同样用大 OO 符号表示。

                包括算法显式内存(变量和数据结构)和隐式占用栈空间(递归调用)

        Example:

                1.若算法需要额外创建一个长度为n的数组，则空间复杂度为O(n)

                2.O(1): 交换两个变量的值

void swap(int* a, int* b){
    int temp = *a;    // 仅使用一个临时变量
    *a = *b;
    *b = temp;
}

                3.O(n) : 归并排序

                4.递归栈空间O(n): 递归计算阶乘

double factorial(int n){
    double ans = 1;
    if(n == 0 || n == 1) return 1;
    else return n * factorial(n);    // 递归深度为n
}

                递归调用栈的最大深度为 nn，空间复杂度为 O(n)

        (2)如何判断空间复杂度：

                1.分析代码：

                        若创建与输入规模相同的数组        -> O(n)

                        若仅使用固定数量的变量                -> O(1)

                2.递归调用的深度：

                        斐波那契递归的空间复杂度为 O(n) (最大调用深度为 n）

                        快速排序的平均递归深度为 O(log⁡n), 空间复杂度为 O(log⁡n)

                3.动态内存分配