数据结构java版第1章-PPT课件.ppt

第1章算法分析
算法
时间复杂度Big-O
思考题
1
算法
数组元素相加
矩阵相加
矩阵相乘
顺序查找
2
算法
算法(Algorithm)是一个解决问题的有限步骤过程,也可以说是在解答过程中的一步步过程。
数组元素相加
数组元素相加是将数组中每个元素的值加起来,其所对应的Java程序如下:
public static int sum(int arr[],int n)
{
int i,total=0;
for(i=0;i<n;i++)
total+=arr[i];
return total;
}
3
矩阵相加
矩阵相加表示将相对应的元素相加, ,
程序如下:
public static void add(int a[][],int b[][],int c[][],int m,int n)
{
for (int i=0; i < n; i++)
for (int j=0; j < n; j++) c[i][j] = a[i][j] + b[i][j]
}
4
矩阵相乘
矩阵相乘为, ,
对应的程序如下:
public static void mul(int a[][], int b[][], int c[][], int n)
{
int i,j,k,sum;
for(i=0; i < n; i++)
for(j=0;j<n;j++){
sum=0;
for(k=0;k<n;k++)
sum=sum+a[i][k]*b[k][j];
c[i][j]=sum;
}
}
5
顺序查找
顺序查找是指在一个数组中,由第1个元素开始依次查找,我们假设要找的数据一定在数组中,其程序如下:
public static int search(int data[],int target, int n)
{
int i;
for (i = 0;i < n; i++)
if (target == data[i])
return i;
}
6
练习题
试回答下列程序中x = x+1;语句执行了多少次?
for(i=1;i<=n;i++)
for (j=i;j<=n;j++)
x=x+1;
for (i=1;i<=n;i++){
k=i+1;
do {
x=x+1;
} while(k++<=n);
}
7
时间复杂度Big-O
在程序或算法中,每一条语句(statement)的执行时间为:
①此语句执行的次数;
②每次执行此语句所需的时间。
两者相乘即为此语句的执行时间。
8
Big-O的定义
f(n)=O(g(n)),当且仅当唯一存在正整数c及n0,使得f(n)≤cg(n),对所有的n,n≥n0。
上述的定义表示可以找到c和n0,使得f(n)≤c×g(n),此时,我们称f(n)的Big-O为g(n)。
9
常见的Big-O
Big-O
类别
O(1)
常数时间(constant)
O(log2n)
对数时间(logarithmic)
O(n)
线性时间(linear)
O(n2log2n)
对数线性时间(log linear)
O(n2)
平方时间(quadratic)
O(n3)
立方时间(cubic))
O(2n)
指数时间(exponential)
O(n!)
阶乘时间(factorial)
O(nn)
n的n次方时间
10