自己架设网站服务器,制作网站的方法有哪些内容,手机怎么做网站卖东西,美食网页设计模板国内版目录
1 时间复杂度
2 大O渐进表示法
举例子#xff08;计算时间复杂度为多少#xff09;
3 空间复杂度 前言#xff1a;复杂度分为时间复杂度和空间复杂度#xff0c;两者是不同维度的#xff0c;所以比较不会放在一起比较#xff0c;但是时间复杂度和空间复杂度是用…目录
1 时间复杂度
2 大O渐进表示法
举例子计算时间复杂度为多少
3 空间复杂度 前言复杂度分为时间复杂度和空间复杂度两者是不同维度的所以比较不会放在一起比较但是时间复杂度和空间复杂度是用来衡量一个算法是否好坏的标准时间复杂度用来描述算法运行的时间快慢空间复杂度用来衡量一个算法所需要的额外空间。最初的计算机时代计算机的存储量很小所以额外注重空间复杂度随着发展计算机的存储已经不是让人担心的点了所以更为注重时间复杂度。 1 时间复杂度
时间复杂度的定义上可以认为使劲按复杂度是一个函数定量的描述了算法所需要的时间但是理论上来说运行的时间是要上机测试才能测试出来的实际测试就会花很多时间所以有了时间复杂度这个分析方式分析算法中执行的基本操作的次数认定为时间复杂度。
int main()
{for (int i 0; i N; i){for (int j 0; j N; j){//测试语句}}for (int i 0; i N; i){//测试语句}int M 10;while (M--){//测试语句}return 0;
}
这段代码的时间复杂度是
两个嵌套的for循环也就是执行了N^2次再来一个for循环执行次数为N最后while收尾执行次数为10,所以时间复杂度的函数为F(N) N^2 N 10随着N的增大式子的值会大到无法想象 这都得益于N^2那么整个式子的决定性因素是N^2所以我们就认为时间复杂度是N^2。
这种估算的方法被称为大O渐进表示法只取式子中的决定性因素。 2 大O渐进表示法
计算时间复杂度的时候我们通常采用大O渐进表示法推导大O阶的表示方法为
1、用常数1取代运行时间中的所有加法常数。
2、在修改后的运行次数函数中只保留最高阶项。
3、如果最高阶项存在且不是1则去除与这个项目相乘的常数。得到的结果就是大O阶。
这里其实完全可以类比高中的数学函数y xx可以是2x也可以是3x这就是为什么舍弃常数的原因x和2x是没有区别的。
那么什么是加法常数呢只要没有循环或者递归我们都可以认为执行次数为O(1)哪怕是写了一万行代码。
执行程序的时候会存在最好情况 最坏情况 以及平均情况期望值一般计算时间复杂度的时候都是计算的最坏情况所以像冒泡排序运气好点时间复杂度就是O(1),运气不好就是O(N^2)了。
举例子计算时间复杂度为多少
void Func2(int N)
{int count 0;for (int k 0; k 2 * N; k){count;}int M 10;while (M--){count;}printf(%d , count);
}
第一个for循环的执行次数为2 * N次第二个while循环执行次数为10次那么函数表达式就是2*N 10,根据大O表示法时间复杂度为O(N)。
void Fun3(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 , count);
}
第一个for循环执行次数为M次第二个for循环的执行次数为N次那么函数表达式就是O(M N)
那么最后结果视结果而定如果M远大于N那么时间复杂度就是O(M)那么N M同理可得。
void Func4(int N)
{int count 0;for (int k 0; k 100; k){count;}printf(%d, count);
}
根据第一个for循环的循环条件循环次数为100次是常数所以时间复杂度就是O(1)。
void BubbleSort(int* a, int n)
{assert(a);for (size_t end n; end 0; end--){int flag 0;for (size_t i 1; i end; i){if (a[i - 1] a[i]){swap(a[i - 1], a[i]);flag 1;}}if (flag 0){break;}}
}
冒泡排序严格意义上来说不是标准的O(N^2)因为它的执行次数在随着程序的执行是逐渐减少的最开始两两比较的次数是N- 1每趟下来就会确定一个数据的位置所以两两比较的次数每次都会减去1那么if这个语句执行的次数就是N - 1 N - 2……1,利用高中的等差数列的知识可以得到时间复杂度的函数是F(N) (N - 1) * (N - 1 1) / 2根据大O表示法可得得出复杂度为O(N^2)。
int BinarySeatch(int* a, int n, int x)
{assert(a);int begin 0;int end n - 1;//[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;elsereturn mid;}return -1;
}这是一个典型的二分查时间复杂度为直接看是看不出来的所以有的代码计算时间复杂度是要结合画图的 我们讨论最坏情况二分查找的本质就是不断的缩小区间一半一半的缩短那么最开始有N个值就有N/2/2/2/2/2/2…… 1那么执行次数就是找的次数就是除以2的次数计算方式就是
N 2^xx是执行的次数我们求的就是x的值那么利用高中的换底公式我们可以得到
x是以2为底N的对数而因为对数不太好写除非使用专业的公式编辑器所以默认规定LogN,表示的就是以2为底N的对数如果有其他底数就照常写。
long long Fac(size_t N)
{if (0 N){return 1;}return Fac(N - 1) * N;
}计算阶乘递归的时间复杂度递归会多次开辟函数栈帧所以一次递归就会开辟一个函数栈帧执行次数是1那么递归n次总执行次数就是N所以时间复杂度就是O(N)。
引申
long long Fac(size_t N)
{if (0 N)return 1;for (int i 0; i N; i){//测试语句}return Fac(N - 1) * N;
}递归函数里面加了一个for循环时间复杂度是多少呢
不加for循环之前每个函数的时间复杂度是O(1)开辟了N个函数那么复杂度就是O(N)但是现在每个函数的时间复杂度就是O(N)了因为每个子函数里面都有一个for循环所以N个O(N)的函数放在一起时间复杂度就是O(N ^ 2)。
long long Fib(size_t N)
{if (N 3)return 1;return Fib(N - 1) Fib(N - 2);
}我们知道递归用来计算斐波那契数列是非常不划算的因为重复计算的次数太多了是次方级别的重复 像这样函数执行的次数是从2的0次方开始一直到2的N次方那么利用高中的等比数列的公式可以得出时间复杂度为函数为F(N) 2^N - 1,所以时间复杂度就是O(2 ^ N)。
这是非常恐怖的所以计算斐波那契数列的话还是使用迭代吧 3 空间复杂度
时间复杂度可以理解为语句的执行次数空间复杂度可以理解额外开辟的空间也是采用的大O渐进表示法。当然空间复杂度不是多少字节意义不大因为当前的计算机存储足够大所以空间复杂度表示的是变量的个数需要注意的是函数需要的栈空间在编译期间就已经确定好了所以计算空间复杂度靠的是程序运行时候显示出来的额外空间。
void BubbleSort(int* a, int n)
{assert(a);for (size_t end n; end 0; end--){int flag 0;for (size_t i 1; i end; i){if (a[i - 1] a[i]){swap(a[i - 1], a[i]);flag 1;}}if (flag 0){break;}}
}
计算冒泡排序的空间复杂度 这个函数里面有变量但是是有限个的如end flag i 并没有额外开辟空间所以空间复杂度是O(1)毕竟是没有额外申请空间的。
那么递归计算斐波那契数列的空间复杂度是多少呢
在此之前我们先看这串代码
void Test1()
{int a 10;printf(%p\n, a);
}
void Test2()
{int b 10;printf(%p\n, b);
}
int main()
{Test1();Test2();return 0;
}
试问运行结果是不是一样的有人就会问了不同函数存的地址肯定不是一样的啊一般情况是这样的但是如果两个函数连续调用并且函数的功能一样对空间的需求是一样的那么内存在栈上的空间分配就不会额外开辟空间也就是说一个函数调用完后另一个函数就会接着使用这块空间所以地址是一样的。
那么类比到斐波那契数列的重复计算里面
long long Fib(size_t N)
{if (N 3)return 1;return Fib(N - 1) Fib(N - 2);
}实际上上开辟的空间都是为了计算函数Fib(N)到Fib(1)的函数的功能是一样对空间的需求也是一样的所以重复计算的时候就不会单独开辟空间所以需要计算的都用了开辟的Fib(N)到Fib(1)的空间那么空间复杂度就是O(N)。 感谢阅读
