赞
踩
目录
对于以下斐波那契数列:
- #define _CRT_SECURE_NO_WARNINGS
-
- #include <iostream>
- using namespace std;
-
- long long fib(int N)
- {
- if (N < 3)
- return 1;
-
- return fib(N - 1) + fib(N - 2);
- }
-
- int main()
- {
-
-
-
- return 0;
- }
用递归实现斐波那契数列,看上去代码十分简洁,但简洁一定就是好算法吗?如何衡量一个算法的好坏?
算法在编写成可执行程序后,运行时需要耗费时间资源和空间(内存)资源。因此衡量一个算法的好坏,一般是从时间和空间两个维度来衡量的,即时间复杂度和空间复杂度。
时间复杂度主要衡量一个算法的运行快慢,而空间复杂度主要衡量一个算法运行所需要的额外空间。在计算机发展的早期,计算机存储容量很小。所以对于空间复杂度很是在乎。但是经过计算机行业的迅速发展,计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要特别关注一个算法的空间复杂度。
定义:在计算机科学中,算法的时间复杂度是一个函数,它定量描述了该算法的运行时间。一个算法执行所耗费的时间,从理论上来讲,是不能算出来的,只有把程序放在机器上跑起来才能知道。但是我们需要每个算法都上机测试吗?固然可以都上机测试,但是这很麻烦,所以才有了时间复杂度这个分析方法。一个算法所花费的时间与其中语句的执行次数成正比例,算法中的基本操作的执行次数,为算法的时间复杂度。
即:找到某条语句与问题规模N之间的数学表达式,就是算出了该算法的时间复杂度。
- #define _CRT_SECURE_NO_WARNINGS
-
- #include <iostream>
- using namespace std;
-
- // 请计算一下Func1中++count语句总共执行了多少次?
- 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;
-
- cout << count << endl;
- }
-
- int main()
- {
-
-
- return 0;
- }
Func1执行的基本操作数:
-> N = 10 F(N) = 130-> N = 100 F(N) = 10210-> N = 1000 F(N) = 1002010
实际我们在计算时间复杂度时,并不一定要计算精确的执行次数,只需要大概执行次数,所以我们使用大O的渐进表示法。
大O符号(Big O notation):是用于描述函数渐进行为的数学符号。
推导大O阶方法:
使用大O的渐进表示法后,Func1的时间复杂度为:
-> N = 10 F(N) = 100
-> N = 100 F(N) = 10000-> N = 1000 F(N) = 1000000
通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项,简洁明了的表示出了执行次数。
另外有些算法的时间复杂度存在最好、平均和最坏情况:
例如:在一个长度为N的数组中搜索一个数据x
在实际中一般情况关注的是算法的最坏运行情况,所以数组中的搜索数据时间复杂度为:
实例1:
- // 计算Func2的时间复杂度?
- void Func2(int N)
- {
- int count = 0;
- for (int k = 0; k < 2 * N; ++k)
- ++count;
-
- int M = 10;
- while (M--)
- ++count;
-
- cout << count << endl;
- }
实例2:
- // 计算Func3的时间复杂度?
- 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;
-
- cout << count << endl;
- }
实例3:
- // 计算Func4的时间复杂度?
- void Func4(int N)
- {
- int count = 0;
- for (int k = 0; k < 100; ++k)
- ++count;
-
- cout << count << endl;
- }
实例4:
- // 计算strchr的时间复杂度?
- const char* strchr(const char* str, int character);
实例5:
- // 计算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;
- }
- }
实例6:
- // 计算BinarySearch的时间复杂度?
- int BinarySearch(int* a, int n, int x)
- {
- assert(a);
- int begin = 0;
- int end = n - 1;
-
- // [begin, end]:begin和end是左闭右闭区间,因此有=号
- while (begin <= end)
- {
- int mid = begin + ((end - begin) >> 1);
- if (a[mid] < x)
- begin = mid + 1;
- else if (a[mid] > x)
- end = mid - 1;
- else
- return mid;
- }
-
- return -1;
- }
实例7:
- // 计算阶乘递归Fac的时间复杂度?
- long long Fac(size_t N)
- {
- if (0 == N)
- return 1;
-
- return Fac(N - 1) * N;
- }
实例8:
- // 计算斐波那契递归fib的时间复杂度?
- long long fib(size_t N)
- {
- if (N < 3)
- return 1;
-
- return fib(N - 1) + fib(N - 2);
- }
答案及分析:
1. 实例1基本操作执行了2N+10次,通过推导大O阶方法知道,时间复杂度为 O(N)2. 实例2基本操作执行了M+N次,有两个未知数M和N,时间复杂度为 O(N+M)3. 实例3基本操作执行了10次,通过推导大O阶方法,时间复杂度为 O(1)4. 实例4基本操作执行最好1次,最坏N次,时间复杂度一般看最坏,时间复杂度为 O(N)5. 实例5基本操作执行最好N次,最坏执行了(N*(N+1)/2次,通过推导大O阶方法+时间复杂度一般看最坏,时间复杂度为 O(N^2)6. 实例6基本操作执行最好1次,最坏O(logN)次,时间复杂度为 O(logN) ps:logN在算法分析中表示是底数为2,对数为N。有些地方会写成lgN。7. 实例7通过计算分析发现基本操作递归了N次,时间复杂度为O(N)。8. 实例8通过计算分析发现基本操作递归了2^N次,时间复杂度为O(2^N)。
空间复杂度也是一个数学表达式,是对一个算法在运行过程中临时占用存储空间大小的量度。
空间复杂度不是程序占用了多少byte的空间,因为意义不大,所以空间复杂度算的是变量的个数。空间复杂度计算规则基本与时间复杂度类似,也是使用大O渐进表示法。
注意:函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了,因此空间复杂度主要通过函数在运行时显式申请的额外空间来确定。
实例1:
- // 计算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;
- }
- }
实例2:
- // 计算fib的空间复杂度?
- // 返回斐波那契数列的前n项
- long long* fib(size_t n)
- {
- if (n == 0)
- return NULL;
-
- long long* arr = (long long*)malloc((n + 1) * sizeof(long long));
- arr[0] = 0;
- arr[1] = 1;
- for (int i = 2; i <= n; ++i)
- arr[i] = arr[i - 1] + arr[i - 2];
-
- return arr;
- }
实例3:
- // 计算阶乘递归Fac的空间复杂度?
- long long Fac(size_t N)
- {
- if (N == 0)
- return 1;
-
- return Fac(N - 1) * N;
- }
答案及分析:
1. 实例1使用了常数个额外空间,所以空间复杂度为 O(1)2. 实例2动态开辟了N个空间,空间复杂度为 O(N)3. 实例3递归调用了N次,开辟了N个栈帧,每个栈帧使用了常数个空间。空间复杂度为O(N)
一般算法的常见复杂度:
5201314 | O(1) | 常数阶 |
3n + 4 | O(n) | 线性阶 |
3n ^ 2 + 4n + 5 | O(n ^ 2) | 平方阶 |
3log(2)n + 4 | O(logn) | 对数阶 |
2n + 3nlog(2)n + 4 | O(nlogn) | nlogn阶 |
n ^ 3 + n ^ 2 + 3n + 4 | O(n ^ 3) | 立方阶 |
2 ^ n | O(2 ^ n) | 指数阶 |
感谢大佬们支持!!!
互三啦!!!
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。