1. 分析时间复杂度

   • 理解基本操作
     • 把算法想象成一个小工厂，里面有各种各样的小工作，这些小工作就是基本操作。像比较两个数的大小、给一个变量赋值、做一次加法或减法，这些都是基本操作。比如说，你要在一个装满玩具的盒子里找一个特定的玩具，每次拿起一个玩具看看是不是你要找的那个，这个“拿起玩具看看”的动作就是基本操作。
   • 数基本操作的次数
     • 现在来看看这些基本操作会做多少次。还是用找玩具的例子，假如盒子里有10个玩具（这10个玩具的数量就是输入规模），你运气不好，要找的玩具在最后一个，那你就得拿起10个玩具一个个看，基本操作就做了10次。如果盒子里有20个玩具，可能就要做20次基本操作。
   • 看操作次数和输入规模的关系
     • 我们把这种关系用时间复杂度来表示。如果基本操作的次数和输入规模（比如玩具的数量）差不多，像刚才找玩具的例子，时间复杂度就是$O(n)$，这里的$n$就是玩具的数量。
     • 再举个例子，如果你要检查两个盒子里的玩具是不是一样（每个盒子里有$n$个玩具），你可能得一个一个地比较，那就要比较$n\times n$次，这种情况时间复杂度就是$O(n^{2})$。
   • 考虑不同情况
     • 最好情况：就像找玩具，运气超级好，你一打开盒子，第一个玩具就是你要找的，这就是最好情况，基本操作只做了1次，时间复杂度是$O(1)$。
     • 最坏情况：和前面说的一样，要找的玩具在最后一个，或者根本不在盒子里，这是最坏情况，时间复杂度可能是$O(n)$或者其他比较复杂的情况。
     • 平均情况：假设玩具在盒子里每个位置出现的可能性都一样，那平均要找一半的玩具，时间复杂度还是$O(n)$。
   • 分析嵌套循环和递归调用
     • 嵌套循环：想象你有一个方阵玩具，要检查每个玩具。你有一个外层循环，用来走方阵的行，还有一个内层循环，用来走方阵的列。如果方阵是$n\times n$大小，外层循环走$n$次，每次外层循环走的时候，内层循环又走$n$次，那总共基本操作（检查玩具）就要做$n\times n$次，时间复杂度就是$O(n^{2})$。
     • 递归调用：递归就像一个会自己不断复制的小机器人。比如说，有一个计算斐波那契数列的递归函数。斐波那契数列是这样的，前两个数是0和1，后面的数是前面两个数的和。如果用递归计算，计算第$n$个数的时候，它会分成计算第$n - 1$个数和第$n - 2$个数，就像树的分支一样，每一层都会分成更多的分支，这样基本操作的次数就会像指数一样增长，时间复杂度是$O(2^{n})$。

2. 优化时间复杂度

   • 换个更好的算法
     • 假如你要给一堆小朋友的身高排序，你一开始用的是冒泡排序，就像比较相邻两个小朋友的身高，高的往后移，这样一轮一轮比较下来，时间复杂度是$O(n^{2})$。但是你发现有个叫快速排序的方法，它的平均时间复杂度是$O(nlogn)$，比冒泡排序快多了，你就可以换用快速排序这个更好的算法。
   • 减少不必要的操作
     • 还是说斐波那契数列，用递归计算的时候，会有很多重复的计算。比如计算第5个数的时候，会算第3个数和第4个数，计算第4个数的时候，又会算第3个数，这样第3个数就被算了好几次。你可以用一个小本本（数组或者变量）把算过的数记下来，下次要用的时候直接看小本本，这样就减少了重复计算，时间复杂度就从指数级变成了$O(n)$。
   • 优化数据结构
     • 假如你有一个很长的队伍（用数组表示），每次有人要插队或者离开队伍，你都得让后面的人往前或者往后移，这样很麻烦，时间复杂度也高。但是如果你用链表来表示这个队伍，有人插队或者离开，只要改一改前后两个人的连接关系就行，时间复杂度就降低了，插入和删除操作的时间复杂度可以是$O(1)$。
   • 利用分治或贪心策略
     • 分治策略：就像你要整理一大箱玩具，你可以把玩具分成几个小堆，先整理好小堆，再把小堆合起来，这样可能会更快。归并排序和快速排序就是这样的，把要排序的数据分成小部分，排好后再合并，这样能降低时间复杂度。
     • 贪心策略：比如你有一堆不同面额的硬币，要凑出一个钱数。贪心策略就是每次都先拿面额最大的硬币，看看能不能凑够，不够再拿面额小一点的。在一些情况下，这种方法能很快地解决问题，降低时间复杂度。

1. 分析时间复杂度
   • 确定基本操作：
     • 首先要明确算法中的基本操作，这些操作通常是对数据进行比较、赋值、算术运算等。例如，在一个数组查找算法中，基本操作可能是比较数组元素与目标元素是否相等。
     • 以简单的线性搜索为例：

bool linearSearch(int arr[], int n, int target) {
    for (int i = 0; i < n; ++i) {
        if (arr[i] == target) {
            return true;
        }
    }
    return false;
}

 - 这里的基本操作是`if (arr[i] == target)`这个比较操作。

• 计算操作次数与输入规模的关系：
  • 观察基本操作执行的次数是如何随着输入规模变化的。在上述线性搜索算法中，输入规模是数组arr的大小n。
  • 在最坏的情况下（目标元素在数组末尾或者不存在），基本操作if (arr[i] == target)会执行n次，所以时间复杂度是$O(n)$。
• 考虑不同情况的复杂度：
  • 除了最坏情况，还可能有最好情况和平均情况。对于线性搜索，最好情况是目标元素在数组的第一个位置，此时基本操作只执行一次，时间复杂度是$O(1)$。
  • 平均情况（假设目标元素在数组中任意位置出现的概率相同）下，平均要检查一半的元素，时间复杂度仍然是$O(n)$。
• 分析嵌套循环和递归调用：
  • 嵌套循环：对于嵌套循环结构，时间复杂度通常是各层循环次数的乘积。例如：

void nestedLoops(int n) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            // 一些操作
        }
    }
}

 - 这里外层循环执行`n`次，对于外层循环的每一次执行，内层循环也执行`n`次，所以总的操作次数是$n\times n=n^{2}$，时间复杂度是$O(n^{2})$。
 - **递归调用**：分析递归调用时，需要考虑递归树的深度和每层的操作次数。例如，简单的斐波那契数列递归实现：

int fibonacci(int n) {
    if (n == 0 || n == 1) {
        return n;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}

 - 递归树的深度是`n`，每层的操作次数（加法操作）随着层数增加而增加，总的操作次数呈指数增长，时间复杂度是$O(2^{n})$。

2. 优化时间复杂度
   • 选择更高效的算法：
     • 例如，对于排序问题，如果使用冒泡排序（时间复杂度为$O(n^{2})$），可以考虑替换为快速排序（平均时间复杂度为$O(nlogn)$）或归并排序（时间复杂度为$O(nlogn)$）。
   • 减少不必要的操作：
     • 避免重复计算。以斐波那契数列为例，上面的递归实现有很多重复计算。可以使用动态规划来避免重复计算：

int fibonacciOptimized(int n) {
    if (n == 0 || n == 1) {
        return n;
    }
    int a = 0, b = 1, c;
    for (int i = 2; i <= n; ++i) {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
}

 - 这个版本的时间复杂度是$O(n)$，通过保存中间结果避免了递归中的重复计算。

• 优化数据结构：
  • 例如，在频繁进行插入和删除操作的场景中，如果使用数组可能导致大量元素移动，时间复杂度较高。可以考虑使用链表，插入和删除操作的时间复杂度可以降低到$O(1)$。
• 利用分治或贪心策略：
  • 分治策略：如归并排序和快速排序都是分治算法的例子。它们将问题分解为更小的子问题，分别解决子问题后再合并结果，通过这种方式降低时间复杂度。
  • 贪心策略：例如，找零问题（使用最少的硬币组合来凑出给定金额），可以使用贪心算法，每次选择面额最大的硬币，直到凑出目标金额。这种策略在某些特定条件下可以有效地降低时间复杂度。

以下是几个C++ 中对数时间复杂度（O(log n)）的计算示例，帮助你更好地理解这种复杂度是如何在实际算法中体现的：

一、二分查找算法

示例代码

#include <iostream>
#include <vector>

// 二分查找函数，在有序数组arr中查找目标元素target
int binarySearch(const std::vector<int>& arr, int target) {
    int left = 0;  // 左边界
    int right = arr.size() - 1;  // 右边界
    while (left <= right) {
        int mid = left + (right - left) / 2;  // 计算中间位置，防止溢出
        if (arr[mid] == target) {
            return mid;  // 找到目标元素，返回其索引
        } else if (arr[mid] < target) {
            left = mid + 1;  // 目标元素在中间元素右侧，更新左边界
        } else {
            right = mid - 1;  // 目标元素在中间元素左侧，更新右边界
        }
    }
    return -1;  // 未找到目标元素，返回 -1
}

int main() {
    std::vector<int> arr = {1, 3, 5, 7, 9, 11, 13};
    int target = 7;
    int result = binarySearch(arr, target);
    if (result!= -1) {
        std::cout << "找到目标元素，索引为: " << result << std::endl;
    } else {
        std::cout << "未找到目标元素" << std::endl;
    }
    return 0;
}

复杂度计算分析

在这个二分查找示例中，每次循环都会将搜索区间缩小一半。假设数组 arr 的长度为 n（这就是输入规模），每经过一次循环比较操作，待搜索的区间长度大致变为原来的一半。

最多经过 log₂n 次比较就能确定目标元素是否存在于数组中。例如，数组长度 n = 8 时，第一次比较后搜索区间缩小为 n = 4，第二次后变为 n = 2，第三次后变为 n = 1，就可以确定元素是否存在了，这里比较了3次，而 log₂8 = 3。

所以，二分查找算法的时间复杂度为 O(log₂n)，在算法复杂度分析中，通常省略底数，记为 O(log n)。其空间复杂度为 O(1)，因为在整个查找过程中，只使用了固定的几个变量（left、right、mid 等）来记录搜索区间和中间位置，所占用的内存空间大小不随输入规模 n 的变化而变化。

二、不断折半的操作（以计算一个数的二进制表示中最高位 1 的位置为例）

示例代码

#include <iostream>

// 计算整数num的二进制表示中最高位1的位置（从右往左数，位置从0开始计数）
int highestOneBit(int num) {
    int pos = 0;
    while (num > 0) {
        num >>= 1;  // 右移一位，相当于除以2
        pos++;
    }
    return pos;
}

int main() {
    int num = 12;  // 二进制表示为 1100
    std::cout << "整数 " << num << " 的二进制表示中最高位1的位置是: " << highestOneBit(num) << std::endl;
    return 0;
}

复杂度计算分析

在 highestOneBit 函数中，每次循环都会将 num 的值右移一位（相当于除以2），操作次数取决于 num 的初始值对应的二进制位数。

对于一个整数 n，它的二进制表示最多有 log₂n + 1 位（例如，8（二进制 1000）对应的 log₂8 + 1 = 4 位）。随着不断右移，每经过一次循环，剩余需要处理的二进制位数就减半，最多经过 log₂n 次操作就能找到最高位1的位置（这里 n 可以理解为输入的整数 num 的大小，即输入规模）。

所以该函数的时间复杂度为 O(log n)，空间复杂度同样为 O(1)，因为只使用了 pos 和 num 这两个固定大小的变量来完成操作，占用的空间不随输入的整数大小而改变。

三、基于分治思想的归并排序中的合并操作（仅分析合并部分体现对数复杂度的情况）

示例代码（仅展示合并部分关键代码）

#include <iostream>
#include <vector>

// 合并两个已排序的子数组，这里假设 [left, mid] 和 [mid + 1, right] 这两个区间内的元素已经有序
void merge(std::vector<int>& arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    std::vector<int> L(n1), R(n2);  // 创建两个临时数组来辅助合并

    // 拷贝数据到临时数组
    for (int i = 0; i < n1; i++) {
        L[i] = arr[left + i];
    }
    for (int j = 0; j < n2; j++) {
        R[j] = arr[mid + 1 + j];
    }

    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k++] = L[i++];
        } else {
            arr[k++] = R[j++];
        }
    }

    // 拷贝剩余元素（如果有的话）
    while (i < n1) {
        arr[k++] = L[i++];
    }
    while (j < n2) {
        arr[k++] = R[j++];
    }
}

复杂度计算分析

在归并排序的合并操作中，重点关注 while (i < n1 && j < n2) 这个循环。每次循环比较两个临时数组 L 和 R 的当前元素，并将较小的元素放入原数组 arr 中，这个过程会不断处理两个子数组中的元素。

两个临时数组 L 和 R 的长度之和大致等于原数组中本次合并的区间长度（假设原数组区间长度为 n，这里 n 就是输入规模相关概念），在每次循环中，都会减少待处理元素的数量，经过大约 log₂n 次比较（每次比较能确定一个元素的最终位置，相当于不断缩小未处理元素的“范围”）就能完成整个合并操作（把两个子数组合并成一个有序数组）。

所以归并排序中合并操作这部分的时间复杂度为 O(log n)，不过整个归并排序算法还包含了不断划分区间的操作等，整体时间复杂度是 O(n log n)，这里仅分析合并操作体现的对数复杂度情况。空间复杂度方面，由于创建了两个临时数组 L 和 R，它们的长度总和与原数组本次合并区间长度相关，大致为 O(n)，但这里只是展示合并操作的空间占用情况，归并排序整体空间复杂度还需要综合考虑其他部分（如递归调用栈等）。

这些示例展示了不同场景下对数时间复杂度的体现，它们的共性是通过不断将问题规模按比例缩小来实现高效的操作，从而使得操作次数与输入规模的对数成正比。

以下是在C++ 中对不同类型算法复杂度进行计算的示例及分析方法，涵盖了常见的几种复杂度情况，主要聚焦于时间复杂度（衡量算法执行时间随输入规模变化的趋势），同时也简单提及空间复杂度（衡量算法运行时占用空间随输入规模变化的趋势）：

一、常数复杂度 - O(1)

• 示例代码：

#include <iostream>

int main() {
    int num = 5;  // 定义一个整型变量，只需执行一次操作
    std::cout << num << std::endl;  // 输出变量，也是一次固定操作
    return 0;
}

• 复杂度分析： 无论程序在什么情况下运行，代码中执行的操作数量都是固定的，不会随着输入规模（这里没有明显的输入规模概念，但如果类比有输入的场景，无论输入如何改变）而变化，所以这个简单程序的时间复杂度是 O(1)。空间复杂度同样为 O(1)，因为只占用了固定大小的内存空间来存储 num 这个变量。

二、线性复杂度 - O(n)

• 示例代码（遍历数组并打印元素）：

#include <iostream>
#include <vector>

void printVector(const std::vector<int>& vec) {
    for (int element : vec) {  // 循环遍历数组，循环次数取决于数组元素个数n
        std::cout << element << " ";
    }
    std::cout << std::endl;
}

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    printVector(vec);
    return 0;
}

• 复杂度分析： 在 printVector 函数中，for 循环会逐个访问向量 vec 中的元素，向量中元素的数量就是输入规模 n。循环执行的次数和 n 相等，随着 n 的增大，操作次数线性增长，所以该函数的时间复杂度为 O(n)。空间复杂度方面，函数内部除了迭代器等极少量固定的临时空间占用外，并没有随 n 增长的额外空间使用，所以空间复杂度为 O(1)（如果忽略编译器等额外可能的少量固定空间开销）。

三、平方复杂度 - O(n²)

• 示例代码（简单的二维矩阵遍历）：

#include <iostream>
#include <vector>

void printMatrix(const std::vector<std::vector<int>>& matrix) {
    for (size_t i = 0; i < matrix.size(); ++i) {
        for (size_t j = 0; j < matrix[i].size(); ++j) {  // 内层循环次数与外层循环的当前轮次相关，整体和矩阵行列数有关
            std::cout << matrix[i][j] << " ";
        }
        std::cout << std::endl;
    }
}

int main() {
    std::vector<std::vector<int>> matrix = {{1, 2}, {3, 4}};
    printMatrix(matrix);
    return 0;
}

• 复杂度分析： 在 printMatrix 函数里存在两层嵌套循环，外层循环执行次数取决于矩阵的行数（假设行数为 n），内层循环每次执行的次数取决于矩阵当前行的列数（假设列数平均也为 n，对于方阵情况就是如此）。那么总的操作次数就是 n×n，随着输入规模（这里体现为矩阵的行列数规模）增大，操作次数以平方的形式增长，所以时间复杂度为 O(n²)。空间复杂度为 O(1)，因为除了固定的循环变量等少量空间占用外，没有因输入规模变化而额外大量占用空间（同样忽略编译器相关固定空间等因素）。

四、立方复杂度 - O(n³)

• 示例代码（三层嵌套循环示例）：

#include <iostream>

void cubeOperation(int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {  // 三层嵌套循环，每层都和输入规模n相关
                std::cout << i << " " << j << " " << k << std::endl;
            }
        }
    }
}

int main() {
    int n = 3;
    cubeOperation(n);
    return 0;
}

• 复杂度分析： 在 cubeOperation 函数中有三层嵌套循环，每层循环都执行 n 次，总的操作次数就是 n×n×n = n³，很明显随着输入规模 n 的增大，操作次数以立方的形式增长，所以其时间复杂度为 O(n³)。空间复杂度上，由于函数内部主要就是循环变量占用空间，这些属于固定的少量空间开销，与 n 无关，所以空间复杂度为 O(1)。

五、对数复杂度 - O(log n)

• 示例代码（二分查找示例，假设已有有序数组 arr 和目标元素 target）：

#include <iostream>
#include <vector>

int binarySearch(const std::vector<int>& arr, int target) {
    int left = 0;
    int right = arr.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;  // 没找到目标元素返回 -1
}

int main() {
    std::vector<int> arr = {1, 3, 5, 7, 9};
    int target = 5;
    std::cout << binarySearch(arr, target) << std::endl;
    return 0;
}

• 复杂度分析： 在 binarySearch 函数中，每次循环都会将搜索区间缩小一半（通过更新 left 和 right 指针来实现）。假设数组 arr 的长度为 n（即输入规模），最多经过 log₂n 次比较就能确定目标元素是否存在（以2为底是因为每次区间缩小一半），所以时间复杂度为 O(log n)，通常省略底数记为 O(log n)。空间复杂度方面，因为只使用了几个固定的变量（left、right、mid 等）来辅助查找，与输入规模 n 无关，所以空间复杂度为 O(1)。

六、指数复杂度 - O(2ⁿ)

• 示例代码（简单的斐波那契数列递归实现，效率较低版本）：

#include <iostream>

int fibonacci(int n) {
    if (n == 0 || n == 1) {
        return n;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);  // 每次递归调用会产生两个分支，导致指数级增长
}

int main() {
    int n = 10;
    std::cout << fibonacci(n) << std::endl;
    return 0;
}

• 复杂度分析： 在 fibonacci 函数中，计算第 n 个斐波那契数时，它会递归地调用自身两次（分别计算 n - 1 和 n - 2 对应的斐波那契数）。随着 n 的增大，这种递归调用分支会呈指数级别的增长，整体的时间复杂度就是 O(2ⁿ)。空间复杂度方面，由于递归调用会在栈上占用空间，随着递归深度（大致和 n 相关）增加，最多可能占用 O(n) 的栈空间（因为每一层递归都需要保存一些局部变量等信息），不过更精确的分析可能涉及到更复杂的斐波那契数列性质等，这里简单可以理解为空间复杂度和时间复杂度在量级上有所关联且随 n 增长。

通过这些不同复杂度的C++ 代码示例，可以更好地理解如何分析和计算算法复杂度，在实际编程和算法设计中，了解复杂度有助于评估算法的性能，进而选择更高效的算法或者对现有算法进行优化。