Comments (2)
时间复杂度分析上
为什么需要复杂度分析: 一般通过代码完成之后,再进行时间统计的方法(事后统计法),受环境影响,受数据规模影响.需要不通过具体的数据来测试,就可以粗略估计出算法的执行效率是最好的。
大O时间复杂度:算法代码执行的时间。代码执行时间随数据规模增长的变化趋势。
// 2n+2 ==> O(n)
int cal(int n) {
int sum = 0; // 1
int i = 1; //1
for (; i <= n; ++i) { // n
sum = sum + i; // n
}
return sum;
}
// 3+n(2+2n) = 2n^2 + 2n + 3 ===> O(n)
int cal(int n) {
int sum = 0; // 1
int i = 1; // 1
int j = 1; // 1
for (; i <= n; ++i) { // n
j = 1; // n
for (; j <= n; ++j) { // n^2
sum = sum + i * j; // n^2
}
}
}
分析方法:
- 只关注循环执行次数最多的代码
- 加法法则 量级最大的
- 乘法法则 嵌套代码的时间复杂度等于内外代码复杂度的乘积
三个方法可能同时用到,相互融合
复杂度量级
非多项式量级只有两个:O(2^n) 和 O(n!)。
NP
当数据规模 n 越来越大时,非多项式量级算法的执行时间会急剧增加,求解问题的执行时间会无限增长。
空间复杂度分析
渐进空间复杂度(asymptotic space complexity),表示算法的存储空间与数据规模之间的增长关系。
课后思考题:
性能测试只能测试出当前代码实现方式的性能数据,没有横行对比,只能看出在一定规模的数据下实现是否满足性能要求,不一定是最优解。通过复杂度分析,可以快速获取当前实现的复杂度大O的表示,我们可以通过分析,确定是否可以寻找更优解。估算大数据下,算法的时间与空间消耗。而且,性能测试受当前机器性能或内存影响,不同机器运行结果可能不同,更大数据规模很难通过测试完成或者耗时较长。
from dsalearn.
复杂度分析 下
最好情况时间复杂度(best case time complexity)、最坏情况时间复杂度(worst case time complexity)、平均情况时间复杂度(average case time complexity)、均摊时间复杂度(amortized time complexity)
不同情况下,不同的时间复杂度
摊还分析法:均摊时间复杂度
最好最坏时间复杂度
// n 表示数组 array 的长度
int find(int[] array, int n, int x) {
int i = 0;
int pos = -1;
for (; i < n; ++i) {
if (array[i] == x) pos = i;
}
return pos;
}
最好: O(1) 第一个, 最坏 O(n)不存在
平均时间复杂度
发生的概率乘以复杂度, 求和。
加权平均值、即期望值的求法。
均摊时间复杂度
// array 表示一个长度为 n 的数组
// 代码中的 array.length 就等于 n
int[] array = new int[n];
int count = 0;
void insert(int val) {
if (count == array.length) {
int sum = 0;
for (int i = 0; i < array.length; ++i) {
sum = sum + array[i];
}
array[0] = sum;
count = 1;
}
array[count] = val;
++count;
}
每n个O(1)之后是O(n), 均摊O(1)
对一个数据结构进行一组连续操作中,大部分情况下时间复杂度都很低,只有个别情况下时间复杂度比较高,而且这些操作之间存在前后连贯的时序关系,这个时候,我们就可以将这一组操作放在一块儿分析,看是否能将较高时间复杂度那次操作的耗时,平摊到其他那些时间复杂度比较低的操作上。
课后思考题:
// 全局变量,大小为 10 的数组 array,长度 len,下标 i。
int array[] = new int[10];
int len = 10;
int i = 0;
// 往数组中添加一个元素
void add(int element) {
if (i >= len) { // 数组空间不够了
// 重新申请一个 2 倍大小的数组空间
int new_array[] = new int[len*2];
// 把原来 array 数组中的数据依次 copy 到 new_array
for (int j = 0; j < len; ++j) {
new_array[j] = array[j];
}
// new_array 复制给 array,array 现在大小就是 2 倍 len 了
array = new_array;
len = 2 * len;
}
// 将 element 放到下标为 i 的位置,下标 i 加一
array[i] = element;
++i;
}
最好: O(1)
最坏: O(n)
均摊复杂度 O(1)
from dsalearn.
Related Issues (4)
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from dsalearn.