三河建设厅公示网站,网页设计师技术水平证书,网站开发数据库有关合同,wordpress 优化js文章目录 算法复杂度时间复杂度1. 定义2. 表示方法3. 常见时间复杂度4.案例计算分析冒泡排序二分查找斐波那契数列#xff08;递归法#xff09;斐波那契数列#xff08;迭代法#xff09; 空间复杂度案例分析冒泡排序斐波那契数列#xff08;递归法#xff09;斐波那契数… 文章目录 算法复杂度时间复杂度1. 定义2. 表示方法3. 常见时间复杂度4.案例计算分析冒泡排序二分查找斐波那契数列递归法斐波那契数列迭代法 空间复杂度案例分析冒泡排序斐波那契数列递归法斐波那契数列(迭代法) 时间复杂度对比 正文 算法
算法(Algorithm):就是定义良好的计算过程他取⼀个或⼀组的值为输⼊并产⽣出⼀个或⼀组值作为输出。简单来说算法就是⼀系列的计算步骤⽤来将输⼊数据转化成输出结果。
程序数据结构算法一个好的程序需要有一个好的算法那如何去衡量一种算法的好坏呢这就需要我们计算算法的复杂度。
复杂度
复杂度是计算机科学中的一个基础概念它帮助我们理解和评估算法的效率对于算法设计和优化至关重要。算法的复杂度通常分为时间和空间复杂度两个方面。
时间复杂度 1. 定义
在计算机科学中算法的时间复杂度是⼀个函数式T(N)它定量描述了该算法的运⾏时间。时间复杂度是衡量程序的时间效率那么为什么不去计算程序的运⾏时间呢
1.因为程序运⾏时间和编译环境和运⾏机器的配置都有关系⽐如同⼀个算法程序⽤⼀个⽼编译器进⾏编译和新编译器编译在同样机器下运⾏时间不同。
2.同⼀个算法程序⽤⼀个⽼低配置机器和新⾼配置机器运⾏时间也不同。
3.并且时间只能程序写好后测试不能写程序前通过理论思想计算评估。 2. 表示方法
如定义所示时间复杂度是一个函数式T(N)T(N)通过表示程序的指令的执行次数来定量描述程序的运行时间。
例如T(N)10T(N)2N10T(N)N2等等等都是描述一个程序指令的执行次数
但是设想一下采用这样的表示方法如果两种算法一种T(N)N2另一种T(N)N2100当N越大时二者差距就可以忽略不计如果我们仍然这样表示不免缺乏简洁性和统一性。
大O渐进表示法
在这基础上我们联想数学中所学的等阶无穷大概念数学中使用小o来表示高阶无穷小而采用大O来表示等阶无穷大。具体的来说对于函数T(N)当N趋于无穷时我们能否找到这样一个函数f(N)使得 T ( N ) f ( N ) \frac{T(N)}{f(N)} f(N)T(N)为一个常数答案是可以的。 3. 常见时间复杂度
下面列出了一些常见时间复杂度O(N)的表示法即f(N)的常见形式。
常数时间复杂度O(1)表示算法的执行时间不随输入规模的增长而变化是最理想的情况。对数时间复杂度O(log n)通常出现在二分查找等分治算法中。线性时间复杂度O(n)表示算法的执行时间与输入规模成正比。线性对数时间复杂度O(n log n)通常出现在快速排序、归并排序等分治算法中。平方时间复杂度O(n2)通常出现在嵌套循环的算法中。指数时间复杂度O(2n)通常出现在递归算法中。多项式时间复杂度O(nk)k可能是大于 2 的正整数这意味着算法在大规模数据上的性能下降较快。 4.案例计算分析
冒泡排序
// 计算BubbleSort的时间复杂度
void BubbleSort(int* a, int n)
{assert(a);for (size_t end n; end 0; --end){int exchange 0;for (size_t i 1; i end; i){if (a[i-1] a[i]){Swap(a[i-1], a[i]);exchange 1;}}if (exchange 0)break;}
}最好情况若数组有序
T(N) N
最差情况若数组与要求顺序反序
T(N) N ∗ ( N − 1 ) 2 \frac{N*(N-1)}{2} 2N∗(N−1)
有n个元素需要排n-1趟第i趟需要排n-i次
即(n-1)(n-2)……1结果如上所示
我们发现上述第一种是最好情况而第二种是最坏情况俗话说的好“做最好的准备做最坏的打算”所以很合理的我们应该将最坏的情况计算结果当做时间复杂度上述即T[N]N2。 二分查找
// 计算BinarySearch的时间复杂度
int BinarySearch(int* a, int n, int x)
{assert(a);int begin 0;int end n - 1;while (begin end){int mid begin ((end - begin) 1);if (a[mid] x)begin mid 1;else if (a[mid] x)end mid;elsereturn mid;}return -1;
}最好情况 O(1) 最坏情况 O(logN) 一次对半筛选当数据很多时筛选k次才找到2kN对数函数增长规律一样为了保持统一性下标可以忽略建议写法即为logN。 斐波那契数列递归法
// 计算斐波那契递归Fib的时间复杂度
long long Fib(size_t N)
{if (N 3)return 1;return Fib(N - 1) Fib(N - 2);
}以此类推即为O(2N)。
斐波那契数列迭代法
long long Fib(size_t n)
{int a 1;int b 1;int c 1;while (n 2){c a b;a b;b c;n--;}return c;
}可见我们使用迭代的方法将时间复杂度降为了O(N)。 空间复杂度
类比时间复杂度相似内容不再过多赘述了 空间复杂度也是⼀个数学表达式是对⼀个算法在运⾏过程中因为算法的需要额外临时开辟的空间。 空间复杂度不是程序占⽤了多少bytes的空间因为常规情况每个对象⼤⼩差异不会很⼤所以空间复杂度算的是变量的个数。 注意函数运⾏时所需要的栈空间(存储参数、局部变量、⼀些寄存器信息等)在编译期间已经确定好了因此空间复杂度主要通过函数在运⾏时候显式申请的额外空间来确定! 案例分析 下面我们用具体案例来熟悉空间复杂度的计算 冒泡排序
// 计算BubbleSort的时间复杂度
void BubbleSort(int* a, int n)
{assert(a);for (size_t end n; end 0; --end){int exchange 0;for (size_t i 1; i end; i){if (a[i-1] a[i]){Swap(a[i-1], a[i]);exchange 1;}}if (exchange 0)break;}
}我们只申请了常数个变量所以很显然空间复杂度为O(1) 斐波那契数列递归法
// 计算斐波那契递归Fib的时间复杂度
long long Fib(size_t N)
{if (N 3)return 1;return Fib(N - 1) Fib(N - 2);
}空间复杂度为O(N)当我们输入N时第一步递归将会沿着N-1N-2一直到3递推在n为3这个函数栈帧里调用2和1并返回给3注意此时1和2的函数栈帧已经销毁以此类推返回一个销毁一个程序在执行时同一时刻实际使用的空间不会超过n个(即往下递推的深度),只是每个n值相同函数栈帧在不同时刻执行了一次又一次的销毁创建过程即在时间复杂度里面我们所讨论的调用次数的问题但在空间复杂度中我们只关心使用的空间故为O(N)。 斐波那契数列(迭代法)
long long Fib(size_t n)
{int a 1;int b 1;int c 1;while (n 2){c a b;a b;b c;n--;}return c;
}这个也很显而易见了为O(1)。 时间复杂度对比 下面是常见时间复杂度对比
