数据结构(一):结构概念 与 算法概念 及 时间复杂度

2018-02-27 11:45:40来源:https://www.jianshu.com/p/03d04c5fe6e9作者:林塬人点击

分享


数据结构概念
数据结构分为:逻辑结构、物理结构
逻辑结构
集合结构:集合结构中的数据元素除了同属于一个集合外,它们之间没有其他关系
线性结构:数据元素之间是一对一的关系
树形结构:树形结构中元素之间存在一种一对多的层次关系
图形结构:元素是多对多的关系
物理结构(存储结构)
顺序存储:把数据元素存放在地址连续的存储单元里,其数据间的逻辑关系和物理关系是一致的
链式存储:把数据元素存放在任意存储单元里,这组存储单元可以是连续的,也可以是不连续的,通过指针找到下一个存放的地址
算法概念
假设现在要写一个求1+2+3+4+…..+100的程序
int num = 0;
for (int i=1;i<=100;i++){
num+=i;
}
System.out.println(num);

上面算法需要循环100次,当要求加到100000时,循环次数越多计算结果越慢,而采用高斯算法
int sum = 0, i = 1000000;
sum = (1 + i) * i / 2;
System.out.println(sum);



yBeXK.png
算法效率度量方法
事后度量法:通过计算算法开始时间与结束时间
事前分析估算法:分析程序执行代码次数(行数),优秀的算法相比普通算法根据问题输入规模 n 的大小,随着 n 的值越大,时间效率上的差异就越大
函数的渐进增长
假设有算法A与算法B:
算法A----要做2n+3次操作(如执行完一个n次的循环,然后又执行一个n次的循环,最后执行3次赋值运算)
算法B----要做3n+1次操作
当 n>2 时,算法A就开始优于算法B,随着时间增加,算法A比算法B越来越好

在实际算法变化中,我们常忽略这些加法常数
算法时间长度
更多的例子:http://blog.csdn.net/zolalad/article/details/11848739
在进行算法分析时
算法执行次数写为T(n),n是问题规模
从而推导算法时间复杂度记作:T(n) = O(f(n))
用大写的O( )体现算法时间复杂度,随着n增大,T(n)增长最慢为最优算法

推导大O的方法
用常数1取代运行时间中所有加法常数
在修改后的运行次数函数中,只保留最高阶项
如果最高阶项存在且不是为1,则去除常数项
常数阶
该算法运行次数为 f(n) = 3,根据推到大O方法,将常数项3改为1,该算法时间复杂度为 O(1)
int sum = 0, i = 1000000;   /*执行一次*/
sum = (1 + i) * i / 2; /*执行一次*/
System.out.println(sum); /*执行一次*/

线性阶
确定算法的阶次,分析算法的复杂度,关键是分析循环结构的运行情况,下面代码时间复杂度为 O(n),因为循环体中的代码要执行 n 次
int i,n =100;
for (i=0;i<n;i++){
//....
}

对数阶
下面代码每次会执行直到 count > n,每次执行完 count 会乘以 2,得 2的x次方=n 得到 x=log2n,该循环复杂程度为O(logn)
int count = 1;
while(count < n){
count = count * 2;
/* 时间复杂度为 O(1) 的程序步骤序列 */
}

平方阶
单个循环时间复杂度为 O(n),而在循环嵌套内两个循环都执行 n ,则为 O(n的2次方),如下面代码
int i,j,n = 200;
for(i = 0;i < n;i++){
for(j = 0;j < n;j++){
// 时间复杂度为平方阶 O(n的2次方)
}
}

若外循环次数为m,内循环次数为n,则时间复杂度为 O(m*n)
int i, j, m = 300, n = 200;
for (i = 0; i < m; i++) {
for (j = 0; j < n; j++) {
// 时间复杂度为 O(m*n)
}
}

下面代码调用了一个函数,函数的时间复杂度为O(1),所以整体时间复杂度为O(n)
public static void main(String[] args){
int i,n = 200;
for(i = 0;i < n;i++){
fun();
}
}
public static void fun(){
System.out.println();
}

常见的时间复杂度
复杂度大小顺序为:O(1) < O(logn) < O(n) < O(nlogn) < O(n的平方) < O(n的立方) < O(2的n次方) < O(n!) < O(n的n次方)











































执行次数函数非正式术语
12O(1)常数阶
2n+3O(n)线性阶
3*(n平方)+2n+1O(n的平方)平方阶
5log2n+20O(logn)对数阶
2n+3nlog2n+19O(nlogn)nlogn阶
6n的3次方+2n的平方+3n+4O(n的立方)立方阶
2的n次方O(2的n次方)指数阶







最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台