营销型网站建设公司价格,浏览器加速器,510企业网站系统源码,怎样做jsp网站目录
一.前言
二.时间复杂度
1.概念
二.大O的渐进表示法
概念#xff1a;
总结#xff1a;
三.常见时间复杂度计算举例
例1
例2
例3
例4
例5.计算冒泡排序的时间复杂度
例6.二分算法的时间复杂度
例7.阶乘递归Fac的时间复杂度
例8.斐波那契递归的时间复杂度
…目录
一.前言
二.时间复杂度
1.概念
二.大O的渐进表示法
概念
总结
三.常见时间复杂度计算举例
例1
例2
例3
例4
例5.计算冒泡排序的时间复杂度
例6.二分算法的时间复杂度
例7.阶乘递归Fac的时间复杂度
例8.斐波那契递归的时间复杂度
四.常见时间复杂度对比 五.空间复杂度
概念
例1
例2
例3 一.前言
从这篇文章开始C语言的学习就结束了接下来将会开启数据结构与算法的学习。
早期计算机刚被发明出来内存空间并不是很大所以不仅追求程序运行时的时间效率还追求空间效率但发展到今天已经不太追求空间效率了时间效率的追求是不变的。
下面就让我们一起学习时间复杂度和空间复杂度是什么吧~
二.时间复杂度
1.概念 1.时间复杂度是一个函数注意这不是编程语言里的函数而是数学意义上的函数 2.这个函数指的是算法跑的次数的函数并不是算法运行的时间因为同一个算法在不同的机器上运行的时间可能是不同的用算法的运行时间表示时间复杂度是欠妥的 3.一个算法所花费的时间与其中语句的执行次数成正比例算法中的基本操作的执行次数为算法的时间复杂度。 二.大O的渐进表示法 概念 大O符号Big O notation是用于描述函数渐进行为的数学符号。 推导大O阶方法 1、用常数1取代运行时间中的所有加法常数。 2、在修改后的运行次数函数中只保留最高阶项。 3、如果最高阶项存在且不是1则去除与这个项目相乘的常数。得到的结果就是大O阶。 需要注意的是算法运行时可能会存在最好情况最坏情况平均情况这个时候我们取最坏情况时的大O 最坏情况任意输入规模的最大运行次数(上界) 平均情况任意输入规模的期望运行次数 最好情况任意输入规模的最小运行次数(下界) 总结 1.大O里的数就是函数表达式中对结果影响最大的项或是最大的量级所在的项 2.如果这个项的系数不是1那么将它变成1简单来说这个项前面的系数得是1 3.如果函数表达式是个常数不管这个常数多大都写成O( 1 ) 光说不练假把式让我们通过例题来更好的理解上述所说吧~ 三.常见时间复杂度计算举例
例1
// 请计算一下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;}printf(%d\n, count);
} 不难看出 Func1 执行的基本操作次数 F(N)N^22^N10 N 10 F(N) 130 N 100 F(N) 10210 N 1000 F(N) 1002010 显然最大的量级是 N^2 所以时间复杂度为O(N^2) 例2
// 计算Func2的时间复杂度
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);
} F(N)2*N10 影响最大的项为2*N因为它的系数不是1所以要变成1即 时间复杂度O(N) 例3
// 计算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;}printf(%d\n, count);
} F(N)MN 由于并未明确告知M和N的关系所以时间复杂度O(MN) 若M远大于N则为O(M); 若N远大于M则为O(N); 若亮着差不多大则为O(N)或O(M); 例4
// 计算Func4的时间复杂度
void Func4(int)
{int count 0;for (int k 0; k 100; k){count;}printf(%d\n, count);
} F(N)100 这是一个常数所以时间复杂度O(1) 例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;}
} 最好情况 原本已排好序所以进入第二个for循环时不进入if语句所以exchange0直接跳出循环所以时间复杂度O(N) 最坏情况 执行完了所有的循环所以时间复杂度O(N^2) 取最坏情况所以最终的时间复杂度为O(N^2) 如果没有exchange相关语句那么最好情况和最坏情况都是O(N^2) 例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 mid1;else if (a[mid] x)end mid-1;elsereturn mid;}return -1;
} 最好情况 第一次就找到了所以时间复杂度O(1) 最坏情况 找到就剩最后一个数才找到 设数组中有N个数一共找了X次 所以 N/(2*2*2*2.....*2)1 一共X个2即2^XN - XlogN(注意这是一个简写真正的意思是以2为底的N的对数 所以取最坏情况 时间复杂度O(logN) 例7.阶乘递归Fac的时间复杂度
long long Fac(size_t N)
{if(0 N)return 1;return Fac(N-1)*N;
} 不难看出一共会递归N次所以时间复杂度为O(N) 例8.斐波那契递归的时间复杂度
// 计算斐波那契递归Fib的时间复杂度
long long Fib(size_t N)
{if(N 3)return 1;return Fib(N-1) Fib(N-2);
}
对于这种较复杂的时间复杂度的计算可以通过画图来观察 三角形那一块是缺失的部分; 通过上图我们发现一共会执行F(N)2^N-X(这个X是一个常数 所以时间复杂度O(2^N) 四.常见时间复杂度对比
一般算法常见的复杂度如下 五.空间复杂度
概念 1.空间复杂度也是一个数学表达式是对一个算法在运行过程中临时占用存储空间大小的量度 2.空间复杂度不是程序占用了多少bytes的空间因为这个也没太大意义所以空间复杂度算的是变量的个数 3.空间复杂度计算规则基本跟实践复杂度类似也使用大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;}
} 显然上面的代码带上形参共有5个变量根据大O渐进法的规则空间复杂度O(1); 例2
// 计算Fibonacci的空间复杂度
// 返回斐波那契数列的前n项
long long* Fibonacci(size_t n)
{if(n0)return NULL;long long * fibArray (long long *)malloc((n1) * 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;
} 上述代码除了5个变量外还有malloc函数开辟的n1个空间F(N)n6 即空间复杂度O(n) 例3
// 计算阶乘递归Fac的空间复杂度
long long Fac(size_t N)
{if(N 0)return 1;return Fac(N-1)*N;
} 这是一个递归每次进入递归时都会再次创建变量建立栈帧返回时销毁变量上述代码啊一共会递归N次所以会创建N个变量 即空间复杂度O(N) 到此本篇文章就结束了这是数据结构的第一篇文章往后也会继续更新的 若本篇文章有错误或是有建议欢迎小伙伴们提出哦 希望各位大佬们多多支持博主~ 谢谢你的阅读。
