国外网站需要备案,wordpress 音频,网站建设辶金手指谷哥十四,八大装修风格有哪些目录
1. 算法效率
2. 时间复杂度
2.1 时间复杂度概念
2.2 准确的时间复杂度函数式
2.3 大O渐进表示法
2.4 时间复杂度的常见量级
2.5 时间复杂度示例
3. 空间复杂度
3.1 空间复杂度概念
3.2 空间复杂度示例 1. 算法效率
一般情况下#xff0c;衡量一个算法的好坏是…目录
1. 算法效率
2. 时间复杂度
2.1 时间复杂度概念
2.2 准确的时间复杂度函数式
2.3 大O渐进表示法
2.4 时间复杂度的常见量级
2.5 时间复杂度示例
3. 空间复杂度
3.1 空间复杂度概念
3.2 空间复杂度示例 1. 算法效率
一般情况下衡量一个算法的好坏是从时间和空间两个维度来衡量的。
时间复杂度主要衡量一个算法的运行快慢空间复杂度主要衡量一个算法运行需要的额外空间。
2. 时间复杂度
2.1 时间复杂度概念
在计算机科学中算法的时间复杂度是一个函数一个算法所花费的时间与其中语句的执行次数成比例算法中的基本操作的执行次数为算法的时间复杂度。
即找到某条基本语句与问题规模N之间的数学表达式就是算出了该算法的时间复杂度。
注不能直接用运行时间来定义一个算法的时间复杂度一个算法的运行时间与硬件的配置存在联系同样一个算法无法算出准确时间。而时间复杂度与具体机器无关。
2.2 准确的时间复杂度函数式
对于以下代码
void Func1(int N)
{int count 0;for (int i 0; i N; i){for (int j 0; j N; j){count;}}for (int k 0; k 2 * N; k){count;}int M 10;while (M--){count;}printf(%d\n, count);
}
F(N)N*N2*N10这是准确的时间复杂度函数式计算的结果是算法运行的准确次数。
但其意义并不大计算时间复杂度时并不一定要计算出准确的执行次数只需要大概执行次数表示算法效率所在量级即可故而引进大O的渐进表示法。
2.3 大O渐进表示法
当不方便在算法之间比较准确时间复杂度函数式时使用大O的渐进表示法对其进行简化。
简单而言大O渐进表示法是估算一个算法的数量级而非准确数值。
具体而言推导大O阶方法
1用常数1取代运行时间中的所有加法常数O(1)代表常数次而非1次
2在修改后的运行次数函数中只保留最高阶项
3如果最高阶项存在且不是1则去除与这个项目相乘的常数。
得到的结果就是大O阶。
2.4 时间复杂度的常见量级 按数量级递增排列常见的时间复杂度有
O(1)O(log N)O(N)O(Nlog N)O(n^2)O(n^3)...n^kO(2^n)
随着问题规模N的不断增大上述时间复杂度不断增大算法的执行效率越低若复杂度超过O(N^3)则该算法效率已经非常低没有运行的必要。
2.5 时间复杂度示例
示例1
void Func2(int N)
{int count 0;for (int k 0; k 2 * N; k){count;}int M 10;while (M--){count;}printf(%d\n, count);
}
时间复杂度为O(NN时间复杂度准确函数式F(N)2*N10
示例2
void Func3(int N, int M)
{int count 0;for (int k 0; k M; k){count;}for (int k 0; k N; k){count;}printf(%d\n, count);
}
当N、M大小未知时时间复杂度表示为O(NM)
当N远大于M时时间复杂度表示为ON
当M远大于N时时间复杂度表示为OM
当N、M属于一个量级时时间复杂度表示为OM或O(N)均可
示例3
void Func4(int N)
{int count 0;for (int k 0; k 100; k){count;}printf(%d\n, count);
}
时间复杂度表示为O(1)
示例4
const char * strchr ( const char * str, int character );
该算法的时间复杂度最好1次最坏N次时间复杂度一般看最坏情况为ON
注1strstr为字符串查找函数详细内容见下文
【C语言】_字符串查找函数strstr_c语言查找字符-CSDN博客文章浏览阅读147次点赞9次收藏5次。注关于上文strstr函数的模拟实现还有很大优化空间包括但不限于KMP算法本篇仅实现简单的匹配功能暂不考虑效率。2待匹配字符串str2需逐字符在str1中进行对应查找匹配将用于遍历str2的指针变量记为s2类型为char*3str2需与str1中的字符逐字符进行匹配需设遍历str1的指针变量记为s1类型为char*1返回值为第一次匹配的str2在str1中的位置记为cur类型为char*strstr函数功能在str1中查找str2若未找到则返回空指针_c语言查找字符https://blog.csdn.net/m0_63299495/article/details/145165702https://blog.csdn.net/m0_63299495/article/details/145165702https://blog.csdn.net/m0_63299495/article/details/1451657022在算法时间复杂度计算时一般会采取保守估计将最坏情况作为时间复杂度。
最坏情况任意输入规模的最大运行次数(上界) 平均情况任意输入规模的期望运行次数 最好情况任意输入规模的最小运行次数(下界)
例如在一个长度为N数组中搜索一个数据x 最好情况1次找到 最坏情况N次找到 平均情况N/2次找到 在实际中一般情况关注的是算法的最坏运行情况所以数组中搜索数据时间复杂度为O(N)
示例5冒泡排序
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;}
}
时间复杂度准确函数式式F(N) N-1N-2...21((N-11)*(N-1))/2(N*(N-1))/2;
故时间复杂度为O(N^2)
示例6二分查找
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;
}
二分查找用于有序数组的查找查找区间变化为N - N/2 - N/2/2 - N/2/2/2 - ... - N/2/2/.../2
① 查找的最好情况为查找一次即找到即O1
② 查找的最坏情况为查找区间只剩一个数或没找到即 N/2/2/.../21假设查找了x次即2^xN求得最坏情况为O(log N) 故时间复杂度为O(log N)
注在时间复杂度的表示中log₂N 可简写为 log N不准确表达也有lg N。
在时间复杂度表示中默认 log N 的底数为2。
示例7阶乘
long long Fac(size_t N)
{if (0 N)return 1;return Fac(N - 1) * N;
}
Fac(N)调用Fac(N-1) Fac(N-1)调用Fac(N-2)...Fac(2)调用Fac(1)Fac(1)调用Fac(0)共调用N1次且单次调用复杂度为O(1)递归的时间复杂度是所有递归调用次数的累加 故时间复杂度为O(N);
示例8
long long Fib(size_t N)
{if (N 3)return 1;return Fib(N - 1) Fib(N - 2);
} 复杂度具体函数可以近似为Fib(N)2^0 2^1 2^2 ...... 2^(N-2) 2^(N-1) - 1: 时间复杂度为O(2^N);仅有理论意义实际几乎不用
注当N不是非常大时通常使用循环代替递归计算斐波那契数列可降低时间复杂度为O(N)
long long Fib(size_t N) {long long f1 1;long long f2 2;long long f3 0;for (size_t i 3; i N; i) {f3 f1 f2;f1 f2;f2 f3;}return f3;
}
3. 空间复杂度
3.1 空间复杂度概念
空间复杂度也是一个数学表达式是对一个算法在运行过程中临时占用存储空间大小的量度。
同时间复杂度一样具体占用了多少字节的空间大小没有意义也采用大O渐进表示法空间复杂度计算的是变量个数。
注意函数运行时所需要的栈空间存储参数、局部变量以及一些寄存器信息等在编译期间已经确定好了因此空间复杂度主要通过函数在运行时显示申请的额外空间来确定。
3.2 空间复杂度示例
示例1
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);
示例2
long long* Fibonacci(size_t n)
{if (n 0)return NULL;long long* fibArray (long long*)malloc((n 1) * sizeof(long long));fibArray[0] 0;fibArray[1] 1;for (int i 2; i n; i){fibArray[i] fibArray[i - 1] fibArray[i - 2];}return fibArray;
}
空间复杂度是O(N)
示例3
long long Fac(size_t N)
{if (N 0)return 1;return Fac(N - 1) * N;
}
递归调用了N1次量级为N开辟了N个栈帧每个栈帧使用了常数个空间空间复杂度为O(N)
示例4
long long Fib(size_t N)
{if (N 3)return 1;return Fib(N - 1) Fib(N - 2);
}
时间是累积的空间不累积可以重复利用空间复杂度是O(N)
相较于时间复杂度空间复杂度更为简单通常情况下最常见的空间复杂度有O(1)、O(N)一维数组、O(N^2)二维数组
