东台网络推广,搜索引擎优化什么意思,网站数据库怎么做同步,做网站的网址目录
时间复杂度
什么是时间复杂度
常见时间复杂度类型
如何计算时间复杂度
空间复杂度
什么是空间复杂度
常见的空间复杂度类型
如何计算空间复杂度 时间复杂度和空间复杂度是评估算法性能的两个重要指标。 时间复杂度
什么是时间复杂度 时间复杂度描述了算法执行所需…目录
时间复杂度
什么是时间复杂度
常见时间复杂度类型
如何计算时间复杂度
空间复杂度
什么是空间复杂度
常见的空间复杂度类型
如何计算空间复杂度 时间复杂度和空间复杂度是评估算法性能的两个重要指标。 时间复杂度
什么是时间复杂度 时间复杂度描述了算法执行所需时间随输入规模增长的变化趋势。它通常用大O表示法来描述表示算法在最坏情况下的时间性能。 常见时间复杂度类型
常数时间O(1)。算法执行时间不随输入规模的变化而变化。线性时间O(n)。算法执行时间与输入规模成正比。平方时间O(n^2)。算法执行时间与输入规模的平方成正比通常见于嵌套循环。对数时间O(logn)。算法执行时间随输入规模的增长而缓慢增加常见于分治和二分查找算法。线性对数时间O(nlogn)。算法执行时间是输入规模与对数的乘积常见于快速排序或归并排序。指数时间O(2^n)。算法执行时间随输入规模指数增长常见于暴力搜索。
在大O表示法中logn一般指的是以2为底的对数因为绝大部分都只用考虑二分的情况以其他数为底的情况很少出现。
如何计算时间复杂度
exp.1
//Func1的时间复杂度为O(N)
void Func1(int N)
{int i 0;int count 0;for (i 0; i N; i){count;}int m 10;while (m){--m;}printf(%d\n,count);
}该函数的运行时间主要跟输入的N的大小有关故为O(n)的时间。
至于说下面的执行的m次循环我们是不用理会的因为在输入的N很大的情况m次循环可以被忽略掉。我们算时间复杂度都是关注主要最主要的部分比如说O(n^2 2n) 那么时间复杂度是O(n^2)。
exp.2
//Func2的时间复杂度为O(N)
void Func2(int N)
{int count 0;int i 0;for (i 0; i N; i){count;}for (i 0; i N; i){count;}printf(%d\n,count);
}这里咋一看时间复杂度是O(2n)但其实时间复杂度还是O (n)。
计算机运行的时间是非常快的所以即使n非常大n的常系数对于整个函数的运行时间是微乎其微的。
所以算时间复杂度也不用算n的常系数。
exp.3
//Func3的时间复杂度为O(1)
void Func3()
{int count 0;int i 0;for (i 0; i 100; i){count;}printf(%d\n,count);
}
时间复杂度为O(1)因为是常数次运行。
exp.4
// BubbleSort的时间复杂度为O(N^2)
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;}
}外层循环执行n次内层循环执行n-1次、n-2次...等等差乘等比最会算出来会有n^2所以时间复杂度是O(n^2)。
exp.5
// BinarySearch的时间复杂度O(logN)
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);//使用右移操作符相当于除以2if (a[mid] x)begin mid 1;else if (a[mid] x)end mid;elsereturn mid;}return -1;
}二分查找的时间复杂度是O(logn)就是对n取以二为底的对数。
exp.6
// 阶乘递归Fac的时间复杂度为O(N)
long long Fac(size_t N)
{if (0 N)return 1;return Fac(N - 1) * N;
}递归的次数同样也算进时间复杂度这里递归了n次所以时间复杂度是O(n)。
这里的空间复杂度也是O(n)因为递归调用函数会在栈上多开n块额外的空间。
exp.7
// 斐波那契递归Fib的时间复杂度为O(2^N)
long long Fib(size_t N)
{if (N 3)return 1;return Fib(N - 1) Fib(N - 2);
}以这种方法算斐波那契数列的递归调用次数有点类似算完全二叉树的节点个数。
所以时间复杂度是O(2^n)。
总结
时间复杂度只需大概想想执行次数n的表达式取次数最大的那项也不用理会n的常系数。
如果涉及递归要想想递归函数的执行次数。 空间复杂度
什么是空间复杂度 空间复杂度描述了算法执行过程中所需的额外存储空间量也用大O表示法来描述。 常见的空间复杂度类型
常数空间O(1)。算法使用固定数量的额外空间与输入规模无关。线性空间O(n)。算法使用的额外空间与输入规模成正比。平方空间O(n^2)。算法使用的额外空间与输入规模的平方成正比。对数空间O(logn)。算法使用的额外空间随输入规模的增长而缓慢增加。线性对数空间O(nlogn)。算法使用的额外空间是输入规模与对数的乘积。
如何计算空间复杂度
exp.1
//sum的空间复杂度是O(1)
int sum(int n) {int sum 0;for (int i 0; i n; i) {sum i;}return sum;
}
sum只额外开辟变量sum额外开辟的空间跟输入的n无关所以空间复杂度是O(1)
exp.2
//Func的空间复杂度是O(n)
void Func(int n)
{int* arr (int*)malloc(sizeof(int) * n);//....}
Func使用的空间复杂度是O(n)因为额外开辟的空间与n成正比。
总结
计算空间复杂度只需看使用的额外存储空间与输入数据规模大小的关系比如跟规模无关就是O(1)跟规模成正比就是O(n)其他O(n^2)等同理。 拜拜下期再见
摸鱼ing✨
