时空复杂度的分析

时间复杂度

为什么会有时间复杂度？

在我们日常中，算法是我们用以解决问题的有效手段，而时间复杂度则是衡量一个算法的适用性、可靠性的标准之一。

时间复杂的概念。

语句的执行次数T(n)是输入规模n的一个函数，若存在某一个辅助函数f(n)，
当你趋于无穷大时，有T(n)/f(n)的值是一个不为零的常数，则有T(n)=O(f(n)),这就是算法的时间渐进复杂度。

常见时间复杂度的大小比较

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) <O(n^3) < O(2^n) < O(n!) < O(n^n)

时间复杂度的计算样例。

洛谷P2249
在本题中的数据范围为：1<=n<=10^6 ，0<=q<=10^9 ,1<=m<=10^6, 若是我们直接利用暴力求解，那么时间复杂度为O(nm)=10^11。
然而正常情况下，机器一秒只能运行的数据为10^9，所以最后你将会得到 TLE。所以这时我们需要利用算法吧时间复杂度降下来，我在这里推荐使用二分法。分析：二分查找数量级为log2n，因为处理m个询问O（m）=10^6，log2 10^6=20 ， 因此O（mlogn） = 20*10^6 < 10^9就不会超时。

#include <stdio.h>

int main() {
	long int n, m;
	scanf("%ld %ld", &n, &m);
	long int a[n];

	for (int i = 1; i <= n; i++) {
		scanf("%ld", &a[i]);
	}

	while (m --) {
		long int l = 1, r = n,mid, x;
		scanf("%ld", &x);

		while (l < r) {
			mid = (l + r) / 2;

			if (a[mid] >= x)
				r = mid;
			else
				l = mid + 1;
		}

		if (a[l] == x)
			printf("%ld ", l);
		else
			printf("-1 ");

	}

	return 0;
}

空间复杂度

空间复杂度 (SpaceComplexity)是对一个算法在运行过程中临时占用存储空间大小的量度。. 一个算法在计算机 存储器 上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。

注：初学者了解即可。

最后

以上就是俊秀裙子为你收集整理的时空复杂度的分析时空复杂度的分析的全部内容，希望文章能够帮你解决时空复杂度的分析时空复杂度的分析所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。