珠市口网站建设没有域名的时候建网站

当前位置： 首页 > news >正文

珠市口网站建设,没有域名的时候建网站,平度网站整站优化外包公司,做网站在图片里加文字文章目录 前言什么是算法效率时间复杂度定义作用类比理解 空间复杂度定义作用类比理解 大O表示法为什么需要#xff1f;定义计算步骤1. 计算基本操作的执行次数 T(n)2. 确定 T(n) 的数量级#xff08;按规则#xff09;3. 使用大O表示法表示时间复杂度 常见复杂度O(1)说明案… 文章目录 前言什么是算法效率时间复杂度定义作用类比理解 空间复杂度定义作用类比理解 大O表示法为什么需要定义计算步骤1. 计算基本操作的执行次数 T(n)2. 确定 T(n) 的数量级按规则3. 使用大O表示法表示时间复杂度 常见复杂度O(1)说明案例还有哪些 O(logN)说明案例还有哪些 O(N)说明案例还有哪些 O(N*logN)说明案例还有哪些 O( N 2 N^2 N2)说明案例还有哪些 O( N 3 N^3 N3)说明案例还有哪些 O( 2 N 2^N 2N)说明案例还有哪些 O(n!)说明案例还有哪些 复杂度比较大小关系图表 常见算法的复杂度解惑补充数学知识-对数和指数指数函数对数函数 省略log(N) 底数为什么复杂度会分3种情况AI算法中的复杂度怎么计算 前言 什么是算法效率 在编写好程序代码之后需要运行在计算机上而在运行过程中需要占用CPU时间片和内存空间。 算法效率是指算法在执行任务时的性能情况。 时间复杂度 定义 时间复杂度可以直观理解为算法运行所需时间与输入规模之间的关系。 作用 用于描述随着输入数据量的增加算法执行所需要的时间将如何增长。 类比理解 如果你要在书架上找一本书你可以有两种方法 顺序查找从书架的第一本书开始一本一本地看直到找到你想要的书。使用目录先在目录中找到书的编号然后直接去相应的位置拿书。 顺序查找的时间复杂度是线性的也就是说如果书架上有n本书在最坏的情况下你可能需要查看所有n本书。我们说这个算法的时间复杂度是O(n)。 而使用目录查找的时间复杂度是常数的不管书架上有多少书你都能很快找到我们说这个算法的时间复杂度是O(1)。 空间复杂度 定义 算法运行时所需内存空间与输入规模之间的关系。 作用 用于描述随着输入数据量的增加算法执行过程中临时占用存储空间的大小。 类比理解 如果你想记录下你已经查找过的书你可能需要一张纸来写下书名 顺序查找这张纸上的记录数量将随着书架上的书数量增加而增加空间复杂度是O(n)。目录查找你可能不需要记录任何东西或者只需要记录一个编号空间复杂度是O(1)。 大O表示法 大O表示法Big O notation是用于描述算法运行时间或空间复杂度的一种数学表示方法。它提供了一种抽象的方式来评估算法的性能尤其是在数据规模增长时算法的表现。 为什么需要 判断一个算法所编程序运行时间的多少并不是将程序编写出来通过在计算机上运行所消耗的时间来度量。原因如下 解决一个问题的算法可能有很多种全部实现的工作量是巨大不可能穷举列出每一种算法不同计算机的软、硬件环境不同即便使用同一台计算机不同时间段其系统环境也不相同程序的运行时间很可能会受影响可能导致结果相差甚远。 所以要通过相同的计算规则来刻画出算法运行效率来评估算法会更加高效。 定义 时间复杂度描述了算法在输入规模 n 增加时运行时间增长的速率。我们用 T(n) 表示算法的运行时间若有一个函数 f(n)使得当n 趋于无穷大时 lim ⁡ n → ∞ T ( n ) f ( n ) \lim_{n \to \infty} \frac{T(n)}{f(n)} limn→∞​f(n)T(n)​ 是一个不等于零的常数则称 f(n) 为T(n) 的同数量级函数记为T(n)O(f(n))。这里O(f(n)) 是算法的渐进时间复杂度。f(n)的形式举例 f(n) 3n1;f(n) 7n^2 1;f(n) 4 n^3 5n^2 3… 计算步骤

1. 计算基本操作的执行次数 T(n) 基本操作是指算法中执行次数最多的操作。基本操作通常是算法中出现次数最多的原子操作如赋值、比较、算术运算等。分析算法最坏的情况下这些操作的执行次数。即算法执行所需的最大时间。
2. 确定 T(n) 的数量级按规则 忽略常数因子在计算时间复杂度时我们忽略常数因子用常数1来取代运行时间中所有加法常数。因为当输入规模n很大时常数因子对算法运行时间的影响可以忽略不计。忽略低阶项我们只保留最高阶的项因为当n趋向于无穷大时最高阶项将决定函数的增长速率。忽略最高阶项的系数与忽略常数因子类似最高阶项的系数在n很大时对增长速率的影响也可以忽略。
3. 使用大O表示法表示时间复杂度 找到一个函数f(n)使得当n趋向于无穷大时T(n)/f(n)的极限是一个非零常数。如果这个条件满足我们就可以说f(n)是T(n)的同数量级函数并用T(n) O(f(n))来表示算法的时间复杂度。 常见复杂度 按上述步骤套案例来理解 O(1) 说明 无论输入数据规模如何执行时间都保持不变。 案例 访问数组中的元素。 在C语言中访问数组元素通常是一个常数时间操作即时间复杂度为O(1)。这是因为数组在内存中是连续存储的每个元素都可以通过其索引直接访问而不需要遍历整个数组。 #include stdio.hint main() {int array[10]; // 声明一个包含10个整数的数组int index, value;// 初始化数组for (index 0; index 10; index) {array[index] index;}// 访问数组元素value array[5]; // 直接访问索引为5的元素printf(The value at index 5 is: %d\n, value);return 0; } 分析 无论数组的大小如何访问数组中任意位置的元素如array[5]的时间是不变的。以下是为什么这是O(1)操作的原因 直接访问数组元素在内存中是连续存储的每个元素的地址可以通过基地址加上偏移量计算得出。偏移量是元素索引乘以元素大小对于整数通常是4或8字节。无需遍历访问特定的数组元素不需要遍历数组中的其他元素。你可以直接使用索引来定位和访问元素。时间不变由于访问任何元素都是通过相同的计算方式这个操作的时间不会随着数组大小的增加而增加。 还有哪些 数组访问如前所述通过索引访问数组中的元素。哈希表操作 插入一个新元素平均情况下。删除一个元素平均情况下。查找一个元素平均情况下。 栈操作 压栈push。出栈pop。查看栈顶元素。 队列操作对于循环队列或双端队列 入队enqueue。出队dequeue。查看队头或队尾元素。 链表操作在已知节点的情况下 插入一个新节点在已知前驱节点的情况下。删除一个节点在已知前驱节点的情况下。 树操作在已知节点的情况下对于特定类型的树 插入或删除节点在二叉搜索树中如果树是平衡的。查找节点在二叉搜索树中。 变量赋值给一个变量赋值。交换两个变量的值。计数器增加或减少。访问固定大小的集合或映射中的元素例如访问固定大小的哈希表。 O(logN) 说明 表示算法的时间复杂度是输入规模 N 的对数。这里的对数通常是基数为 2 的对数即 log₂N但在 Big O 表示法中我们通常忽略基数因为它对于复杂度的渐进分析并不重要。 通常与那些能够通过每次操作减少问题规模的方式通常是减半的算法相关。这种类型的算法在处理大数据集时非常高效因为它们能够在相对较少的操作次数内完成任务。 理解 对数增长速度 当 N 增加时log(N) 的值增长得非常缓慢。例如 如果 N 2则 log₂N 1 如果 N 4则 log₂N 2 如果 N 8则 log₂N 3 如果 N 16则 log₂N 4 以此类推N 每翻倍log₂N 只增加 1。 效率 O(log(N)) 复杂度的算法是非常高效的特别是当 N 非常大时。这是因为算法执行的操作次数几乎不会随着输入规模的增长而显著增加
   案例 二分查找法。 下面是用 C 语言实现二分查找的代码并附上其时间复杂度说明c #include stdio.h// 二分查找函数 int binarySearch(int arr[], int size, int target) {int left 0;int right 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; // 目标在右侧elseright mid - 1; // 目标在左侧}return -1; // 未找到目标 }int main() {int arr[] {2, 3, 4, 10, 40};int size sizeof(arr) / sizeof(arr[0]);int target 10;int result binarySearch(arr, size, target);if(result ! -1) {printf(元素在索引 %d 处找到。\n, result);} else {printf(元素未被找到。\n);}return 0; }分析 基本操作 在二分查找中基本操作是比较目标值与数组中间元素arr[mid]的大小。这一操作在每一次迭代中执行一次。比较 目标值 target 和 arr[mid]。 最多执行次数 为了确定 T(n)我们需要知道在最坏情况下算法需要执行多少次基本操作。 初始规模数组大小为 n。每次迭代将数组的查找范围缩小一半。具体变化为n→n/2→n/4→…查找范围缩小到1即剩余一个元素需要检查说明数组最后只剩下一个元素。 整个算法最多需要执行多少次基本操作取决于我们要将 n 缩小到 1 需要多少次减半操作。 计算这个次数 令 k 为需要执行的迭代次数使得 n / 2 k 2^k 2k 1方程求解 k log ⁡ 2 n \log_2n log2​n 所以T(n) log ⁡ 2 n \log_2n log2​n。 使用大 O 表示法表示时间复杂度 通过上述分析我们知道二分查找的操作次数为 log ⁡ 2 n \log_2n log2​n。在大 O 表示中常数因子不影响量级因此时间复杂度为 T(n) log ⁡ 2 n \log2n log2​n。 在二分查找中每次迭代都会将待查询的范围减半。这种“对半分”的策略使得每经过一次迭代问题规模就减少一半。这种复杂度能够保证即使在非常大的数据集合中查找操作仍能快速完成是因为对数增长的速度非常缓慢。 还有哪些 二分查找Binary Search在有序数组中查找一个特定的元素。平衡二叉搜索树Balanced Binary Search Tree操作包括查找、插入和删除。平衡树如 AVL 树、红黑树等保证了操作的时间复杂度为 O(log(N))。堆Heap操作在二叉堆如最小堆或最大堆中进行插入、删除最小/最大元素以及构建堆等操作。BSTBinary Search Tree中的成功者/失败者树操作用于查找第 k 大/小的元素。在决策树中进行决策如果决策树是平衡的那么找到最终决策的时间复杂度是 O(log(N))。幂运算计算 a 的 b 次幂其中 b 是整数可以通过快速幂算法在 O(log(N)) 时间内完成这里 N 是 b。 O(N) 说明 O(N) 时间复杂度是用于描述算法运行时间随输入规模增长的关系的一种度量方式。这里 N 通常代表输入数据的规模例如数组的大小、列表的长度等。 理解 O(N) 描述的是一种线性关系意味着如果输入规模 N 增加一倍算法的运行时间大致也会增加一倍。O(N) 时间复杂度与 N 的具体值无关而与 N 的增长速率有关。因此无论 N 是 10、100 还是 1000只要输入规模增长算法的运行时间也会以相同的速率增长。 案例 单层循环 #include stdio.hint main() {int n;// 假设n已经被赋值for (int i 0; i n; i) {// 基本操作printf(%d\n, i);}return 0; } 分析 基本操作是 printf(“%d\n”, i);。确定数量级这个基本操作在for循环中执行了n次 此时f(n) n。大O表示运行时间 T(n)O(f(n)) 等价于 T(n)O(n)最终时间复杂度是O(n)。 还有哪些 遍历数组或列表对一个长度为 N 的数组或列表进行一次遍历。线性搜索在未排序或已排序的数组中查找一个元素需要遍历整个数组。链表的遍历遍历一个链表需要访问每个节点一次。 O(N*logN) 说明 表示算法的运行时间与输入规模 N 成正比并且还与 N 的对数成正比。这个复杂度通常出现在算法同时具有一个线性N和一个对数logN的步骤。 理解 分治策略许多分治算法具有 O(N*logN) 的时间复杂度。这些算法通常将问题分成更小的部分然后递归地解决这些部分。两层循环想象一个算法它包含一个循环该循环内部还有一个循环。如果外层循环是线性的N 次迭代而内层循环是对数复杂度的例如每次迭代将问题大小减半那么总的时间复杂度将是 O(N*logN)。 实际应用 在现实世界中O(NlogN) 的算法通常比 O(N^2) 的算法更高效特别是当 N 变得非常大时。例如快速排序和归并排序通常比冒泡排序和插入排序更受欢迎因为它们在大数据集上的性能更好。 案例 #include stdio.hvoid swap(int a, int* b) {int t *a;*a *b;*b t; }int partition(int arr[], int low, int high) {int pivot arr[high]; // 选取最后一个元素作为基准int i (low - 1); // 较小元素的索引for (int j low; j high - 1; j) {// 如果当前元素小于或等于 pivotif (arr[j] pivot) {i; // 增加较小元素的索引swap(arr[i], arr[j]);}}swap(arr[i 1], arr[high]);return (i 1); }void quickSort(int arr[], int low, int high) {if (low high) {// pi 是分区索引arr[pi] 现在在正确的位置int pi partition(arr, low, high);// 分别递归地排序元素quickSort(arr, low, pi - 1); // 递归排序左子数组quickSort(arr, pi 1, high); // 递归排序右子数组} }int main() {int arr[] {10, 7, 8, 9, 1, 5};int n sizeof(arr) / sizeof(arr[0]);quickSort(arr, 0, n - 1);printf(Sorted array: \n);for (int i 0; i n; i) {printf(%d , arr[i]);}printf(\n);return 0; } 分析 基本操作的执行次数在最坏情况下比较次数是 n ( n − 1 ) 2 \frac{n(n-1)}{2} 2n(n−1)​T(n) 的数量级在最坏情况下 T 比较 ( n − 1 ) ( n − 2 ) … 1 n ( n − 1 ) 2 T{\text{比较}} (n-1) (n-2) \ldots 1 \frac{n(n-1)}{2} T比较​(n−1)(n−2)…12n(n−1)​大 O 表示法在最坏情况下快速排序的时间复杂度是O( n 2 n^2 n2)但平均情况下是O(n*logn) 还有哪些 归并排序Merge Sort递归地将列表分成两半排序后合并。快速排序平均情况Quick Sort通过选择一个“基准”元素将数组划分为两部分并递归排序。堆排序Heap Sort构建一个堆数据结构然后不断删除最大值或最小值并重建堆。TimsortPython 的排序算法结合归并排序和插入排序的优点最坏情况下为 O(N*log⁡N)。 O( N 2 N^2 N2) 说明 指算法的执行时间与输入规模 N 的平方成正比。即随着输入规模增大算法的运行时间会以平方倍数增长。 平方关系 意味着如果输入规模翻倍算法的运行时间将增加到原来的四倍。例如如果 N 从 10 增加到 20运行时间将增加到原来的 4 倍因为 2 0 2 20^2 202/ 1 0 2 10^2 102 4。 O( N 2 N^2 N2) 的算法通常不适合处理大规模数据集因为它们的运行时间会随着数据规模的平方增长而变得过长。 案例 双层循环 #include stdio.hint main() {int n;// 假设n已经被赋值for (int i 0; i n; i) {for (int j 0; j n; j) {// 基本操作printf(%d %d\n, i, j);}}return 0; } 分析 基本操作是 printf(“%d %d\n”, i, j);。确定数量级外层循环执行n次内层循环也执行n次所以基本操作执行了n * n n 2 n^2 n2次 此时f(n) n 2 n^2 n2。大O表示运行时间 T(n)O(f(n)) 等价于 T(n)O( n 2 n^2 n2)最终时间复杂度是O( n 2 n^2 n2) 。 因此时间复杂度是O( n 2 n^2 n2)。 还有哪些 冒泡排序Bubble Sort重复扫描列表每次比较相邻元素并交换位置。选择排序Selection Sort每次遍历未排序的部分选择最小或最大元素放到已排序部分的末尾。插入排序Insertion Sort构建有序序列对于未排序数据在已排序序列中从后向前扫描找到相应位置并插入。矩阵乘法Naive Matrix Multiplication两个N×N 矩阵相乘需要进行三重嵌套循环。Floyd-Warshall算法计算所有节点对最短路径用于图中的最短路径问题。穷举算法Brute Force在某些问题中通过穷举所有可能的解决方案来找到答案。双重循环遍历任何涉及双重循环遍历列表中所有元素对的算法如寻找特定条件满足的所有元素对。 O( N 3 N^3 N3) 说明 O(N^3) 算法的执行时间与输入规模 N 的立方成正比。即随着输入规模增大算法的运行时间以立方倍数增长。如果有三个嵌套循环每个循环运行N次总迭代次数就是 N * N * N N 3 N^3 N3。 立方关系 意味着如果输入规模翻倍算法的运行时间将增加到原来的八倍。例如如果 N 从 10 增加到 20运行时间将增加到原来的 8 倍因为 20^3 / 10^3 8。 随着数据规模变大运行时间增长得非常快所以O( N 3 N^3 N3)复杂度的算法在处理大规模数据时通常相当低效。 案例 #include stdio.hvoid tripleLoop(int N) {int i, j, k;int count 0; // 用于计数基本操作的执行次数for (i 0; i N; i) {for (j 0; j N; j) {for (k 0; k N; k) {// 这里是基本操作比如打印或者计数count; // 执行基本操作}}}printf(基本操作的执行次数: %d\n, count); }int main() {int N 10; // 假设 N 的值为 10tripleLoop(N);return 0; } 分析 从计算基本操作的执行次数 在这个例子中基本操作是 count。每次内层循环执行时这个操作都会执行一次。因为内层循环是嵌套在最外层循环中的所以最差情况下基本操作的执行次数是 第一层循环执行 N 次。第二层循环在第一层循环的每次迭代中执行 N 次。第三层循环在第二层循环的每次迭代中执行 N 次。 所以基本操作的执行次数是 N * N * N N^3。 确定T(n)的数量级 T(n) 表示算法运行时间与输入规模 n 的关系。在这个例子中T(n) 与基本操作的执行次数成正比因此 T(n) 的数量级是 N^3。 使用大O表示法表示时间复杂度 因为基本操作的执行次数是 N 3 N^3 N3所以我们可以使用大O表示法将算法的时间复杂度表示为 O( N 3 N^3 N3)。这意味着随着 N 的增加算法的运行时间将按照 N 的立方的速率增长。 还有哪些 矩阵乘法传统的矩阵乘法算法具有 O( N 3 N^3 N3) 的时间复杂度。虽然现代计算机科学中有一些更快的算法如Strassen算法但基本的矩阵乘法仍然遵循 O( N 3 N^3 N3) 的复杂度。多项式相乘两个 degree-N 多项式的经典相乘方法具有 O( N 3 N^3 N3) 的时间复杂度。图的着色某些图着色问题的暴力解决方法可能会达到 O( N 3 N^3 N3) 的时间复杂度。动态规划某些动态规划问题尤其是那些需要三维状态空间的可能会有 O( N 3 N^3 N3) 的时间复杂度。三次方程求解数值方法求解三次方程在某些情况下可能会导致 O( N 3 N^3 N3) 的时间复杂度。高斯消元法在不使用优化的情况下高斯消元法解线性方程组具有O( N 3 N^3 N3) 的时间复杂度。FFT快速傅里叶变换的实现尽管 FFT 本身不是 O( N 3 N^3 N3) 但是某些不正确的实现或者在多维情况下的递归调用可能会导致接近于 O( N 3 N^3 N3) 的性能。 O( 2 N 2^N 2N) 说明 算法的执行时间随着输入规模 N 的指数级增加即时间复杂度是一个指数函数基数为2。 随着 N 增加每增加一个单位运行时间会翻倍。这导致增长非常快。 案例 #include stdio.h// 递归计算斐波那契数列的第 n 个数 long long fibonacci(int n) {if (n 0) {return 0;} else if (n 1) {return 1;} else {return fibonacci(n - 1) fibonacci(n - 2);} }int main() {int n;printf(Enter the value of n: );scanf(%d, n);printf(Fibonacci number at position %d is %lld\n, n, fibonacci(n));return 0; } 分析 计算基本操作的执行次数 在这个递归实现中基本操作是递归函数调用。对于 fibonacci(n)它会调用 fibonacci(n-1) 和 fibonacci(n-2)。每次递归调用都会进行一次加法操作。 确定 T(n) 的数量级 递归斐波那契数列的递归树可以非常直观地展示 T(n) 的数量级。每个递归调用都会生成两个新的递归调用直到达到基本情况。递归树的大小大约是 2^n 因为每个节点都有两个子节点。 使用大O表示法表示时间复杂度 递归斐波那契数列的时间复杂度是 O(2^n)因为每个递归级别都大约是前一个的两倍而递归的深度是 n。 还有哪些 子集生成生成一个集合的所有子集。对于大小为N的集合有 2^N 个可能的子集。幂集与子集生成类似幂集是指一个集合的所有子集的集合因此其大小为 2^N。递归斐波那契数列计算使用简单的递归方法没有记忆化或动态规划优化来计算斐波那契数列的第 N 个数。旅行商问题TSP的暴力解法尝试所有可能的路径组合来找到最短路径对于 N 个城市的 TSP可能的路径数量是 N!但如果只考虑路径的子集则可以认为是O(2^N)。布尔可满足性问题SAT在布尔可满足性问题中如果使用暴力方法尝试所有可能的真值赋值复杂度为O(2^N). 其中 N 是布尔变量的数量。密码学中的穷举攻击在密码学中尝试所有可能的密钥来破解加密信息如果密钥空间是 N 位那么可能的密钥数量是2^N。 O(n!) 说明 算法的执行时间随着输入规模 N 的阶乘增长。阶乘 n! 表示从 1 乘到n 的所有整数的积。 随着 N 的增加运行时间会以非常快的速度增长比指数级的 O(2^N) 还要快。这是因为阶乘增长的速度远远超过多项式、指数甚至双重指数的增长速度。 特点 非常低效对于任何大于很小的n值具有O(n!)时间复杂度的算法在实践中都是不可行的。完全指数级增长n!的增长速度远远超过2n或n2这样的常见复杂度。 示例一个简单的例子是计算所有n个元素的排列。对于n个元素总共有n!种不同的排列方式如果我们要列举出所有排列那么算法的时间复杂度就是O(n!)。 直观感受为什么这么差 考虑n10的情况 10! 3,628,800 这意味着如果有一个O(n!)的算法来处理10个元素它需要进行大约3.6百万次基本操作。 对于更大的n值情况会迅速恶化 20! ≈ 2.43 * 10^18 30! ≈ 2.65 * 10^32
   案例 C语言实现的排列生成算法。该算法使用递归来生成一个包含n个元素的集合的所有可能排列。 #include stdio.hvoid swap(int *x, int *y) {int temp *x;*x *y;*y temp; }void permute(int array, int start, int end) {if (start end) {for (int i 0; i end; i) {printf(%d , array[i]);}printf(\n);} else {for (int i start; i end; i) {swap((array start), (array i));permute(array, start 1, end);swap((array start), (array i)); // backtrack}} }int main() {int n;printf(Enter the number of elements: );scanf(%d, n);int array[n];printf(Enter %d elements: , n);for (int i 0; i n; i) {scanf(%d, array[i]);}printf(All possible permutations are:\n);permute(array, 0, n - 1);return 0; } 分析 基本操作的执行次数 对于排列生成算法每次递归调用都会尝试将每个元素放在当前位置然后递归地排列剩余的元素。对于每个元素我们都需要执行以下操作 交换当前元素与它后面的元素。递归排列剩余元素。再次交换回来以恢复原始状态回溯。 在每一层递归中我们需要进行 n-i 次交换其中 i 是当前的递归深度。在最坏的情况下我们会有 n 层递归每一层递归都会执行 n-i 次交换。 还有哪些 排列生成生成一个集合的所有可能排列。例如生成一个包含n个元素的集合的所有排列会有n!种不同的排列方式。旅行商问题TSP寻找最短路径访问一系列城市并返回起点的最优解。当使用暴力搜索算法时其时间复杂度为O(n!)因为需要考虑所有可能的路径排列。子集和问题在给定的正整数集合中找到所有和为特定值的子集。如果使用穷举所有可能的子集其时间复杂度接近O(n!)。作业调度问题在考虑所有可能的作业顺序时例如当有n个作业需要调度并且每个作业都有特定的处理时间要找到最优的作业顺序其时间复杂度是O(n!)。括号匹配问题生成所有可能的括号匹配序列。例如对于n对括号总共有n!/(n!(n-1)!/2!) n!/(n(n-1)!/2)种可能的匹配方式。组合问题在考虑所有可能的组合时特别是当需要考虑组合的排列时时间复杂度可能会达到O(n!)。 复杂度比较 大小关系 O(1)常数阶 O(logn)对数阶 O(n)线性阶 O(n^2)平方阶 O(n^3)(立方阶) O(2^n) (指数阶) O(n!) (阶乘) 图表 这些算法的复杂度就是数学层面的问题了可以通过图表来进行分析。 图表理解 以下是各个时间复杂度对应的曲线斜率特征 O(1) - 常数阶:曲线斜率为0。这意味着无论输入规模n如何变化算法的运行时间保持不变所以曲线是一条水平线。O(log n) - 对数阶:曲线增长很慢斜率逐渐减小这意味着随着 n 增加性能影响很小。O(n) - 线性阶:曲线是一条斜直线斜率恒定。运行时间直接与 n 成正比。O(n^2) - 平方阶:曲线是抛物线斜率随着 n 增加而线性增加。性能影响比线性算法显著。O(n^3) - 立方阶:曲线斜率增长速度比平方阶更快。随着n的增加曲线的斜率急剧上升表示算法运行时间的增长速度非常快。O(2^n) - 指数阶:曲线斜率以指数速度增长。在指数函数的曲线中随着n的增加斜率几乎垂直上升表明算法运行时间急剧增加。O(n!) - 阶乘阶:曲线斜率增长速度超过所有上述复杂度。阶乘函数的曲线几乎在每一个点上的斜率都比前一个点大得多表明算法运行时间随n的增加而以更快的速度增长。 常见算法的复杂度 PS:之后会针对以上的每一种算法进行详细分析。 解惑 补充数学知识-对数和指数 指数函数 指数函数具有形式f(x) a x a^x ax其中a0 且 a ! 1。 举例 f(x) 2 x 2^x 2x f(0) 2 0 2^0 20 1f(1) 2 1 2^1 21 2f(2) 2 2 2^2 22 4f(3) 2 3 2^3 23 8f(4) 2 4 2^4 24 16 实例分析 举例分析 假设有一个细菌群体每20分钟分裂一次即细菌数量每20分钟翻一番。我们可以用指数函数来描述这个增长过程。 设初始时刻t0细菌数量为P0则t分钟后细菌数量P(t)可以表示为 P(t) P0 * 2^(t/20) 例如如果初始时刻细菌数量为100个那么40分钟后细菌数量为 P(40) 100 * 2^(⁴⁰⁄₂₀) 100 * 2^2 100 * 4 400个 对数函数 对数函数的形式是g(x) log ⁡ a ( x ) \log{a}(x) loga​(x)其中a0 且 a ! 1。 举例g(x) log ⁡ 2 ( x ) \log{2}(x) log2​(x) g(0) log ⁡ 2 ( 0 ) \log{2}(0) log2​(0) 0g(2) log ⁡ 2 ( 2 ) \log{2}(2) log2​(2) 1g(4) log ⁡ 2 ( 4 ) \log{2}(4) log2​(4) 2g(8) log ⁡ 2 ( 8 ) \log{2}(8) log2​(8) 3g(16) log ⁡ 2 ( 16 ) \log_{2}(16) log2​(16) 4 实例分析 现在考虑一个国家的人口增长。在初期由于资源丰富人口增长较快但随着人口数量的增加资源变得有限增长速度逐渐减慢。这种增长模式可以用对数函数来近似描述。 设初始年份t0人口为 P 0 _0 0​ 每年人口增长的比例为固定的r则t年后人口 P(t) 可以表示为 P ( t ) P 0 × ( 1 r ) t P(t) P_0 \times (1 r)^t P(t)P0​×(1r)t 如果我们假设人口增长的比例随人口数量的增加而减少那么人口增长的对数模型可以表示为 log ⁡ ( P ( t ) P 0 ) log ⁡ ( P 0 × ( 1 r ) t P 0 ) log ⁡ ( 1 r ) t t × log ⁡ ( 1 r ) \log \left( \frac{P(t)}{P_0} \right) \log \left( \frac{P_0 \times (1 r)^t}{P_0} \right) \log (1 r)^t t \times \log(1r) log(P0​P(t)​)log(P0​P0​×(1r)t​)log(1r)tt×log(1r) 或者如果我们想表示人口随时间的增长关系可以使用以下指数形式 P ( t ) P 0 × ( 1 r ) t P(t) P_0 \times (1 r)^t P(t)P0​×(1r)t 分析过程 初始条件假设初始年份人口 P 0 _0 0​ 为 100万人, 年增长率为5%。 时间点1第1年末, 人口增长到 100万 × ( 1 0.05 ) 1 \times (1 0.05)^1 ×(10.05)1 105万。 时间点2第2年末, 人口增长到 100万 × ( 1 0.05 ) 2 \times (1 0.05)^2 ×(10.05)2 110.25万。 时间点3第3年末, 人口增长到 100万 × ( 1 0.05 ) 3 \times (1 0.05)^3 ×(10.05)3 115.7625万。
   省略log(N) 底数 为什么计算复杂度log 2 _2 2​(N) 和 log 8 _8 8​(N) 之间的差异只是一个常数它们都被简化为 O(log(N)) 因为不同底数的对数可以相互换算 log ⁡ a ( N ) log ⁡ b ( N ) log ⁡ b ( a ) \log_a(N) \frac{\log_b(N)}{\logb(a)} loga​(N)logb​(a)logb​(N)​ 例如 log ⁡ 10 ( N ) log ⁡ 2 ( N ) log ⁡ 2 ( 10 ) \log{10}(N) \frac{\log_2(N)}{\log2(10)} log10​(N)log2​(10)log2​(N)​ 可以转换成 log ⁡ 10 ( N ) C ⋅ log ⁡ 2 ( N ) \log{10}(N) C \cdot \log_2(N) log10​(N)C⋅log2​(N)其中 C 1 log ⁡ 2 ( 10 ) C \frac{1}{\log_2(10)} Clog2​(10)1​。 所以 O ( C ⋅ log ⁡ 2 ( N ) ) ≡ O ( log ⁡ 2 ( N ) ) ≡ O ( log ⁡ ( N ) ) O(C \cdot \log_2(N)) \equiv O(\log_2(N)) \equiv O(\log(N)) O(C⋅log2​(N))≡O(log2​(N))≡O(log(N)) 为什么复杂度会分3种情况 时间复杂度分为最好情况、一般情况和最坏情况是为了全面理解算法在不同情境下的性能表现 最好情况 这是算法执行得最快的情境。通常由于输入数据已经接近目标算法所需的操作数量最少。分析最好情况有助于了解算法在理想条件下的潜在效率。 一般情况平均情况 反映算法在典型或平均输入条件下的性能。它考虑了所有可能输入的概率分布。这种分析通常更能代表算法的实际性能表现对预期性能评估很重要。 最坏情况 描述算法在最不利输入条件下的性能。这里需要进行最多的操作。这种分析确保算法在任何情况下都能接受并用于保证性能上界。
   AI算法中的复杂度怎么计算 确定关键操作 矩阵运算如矩阵乘法这是大多数 AI 算法的核心计算。激活函数计算激活函数的复杂度。 评估模型规模 层数神经网络的层数和每层的节点数量。参数数量模型的总参数数会影响计算复杂度。 分析训练流程 前向传播每层计算输出的复杂度。反向传播梯度计算的复杂度。 考虑数据规模 样本数每次迭代要处理的训练数据数量。特征数输入数据的维度。 合并计算 单次迭代前向和反向传播的复杂度。总复杂度乘以迭代次数得到总复杂度。