文档介绍：该【算法时间复杂度剖析 】是由【435638】上传分享，文档一共【18】页，该文档可以免费在线阅读，需要了解更多关于【算法时间复杂度剖析 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。1
算法时间复杂度 (The Complexity of Algorithms)
单击此处添加副标题
算法时间复杂度的数学意义
义，给定算法A，如果存在函数f(n)，当n=k时，f(k)表示算法A在输入规模为k的情况下的运行时间，则称f(n)为算法A的时间复杂度。
其中：输入规模是指算法A所接受输入的数据量的多少
算法效率分析
对于同一个算法，每次执行的时间不仅取决于输入规模，还取决于输入的特性和具体的硬件环境在某次执行时的状态。所以想要得到一个统一精确的F(n)是不可能的。为此，通常忽略硬件及环境因素，假设每次执行时硬件条件和环境条件是完全一致的。
影响程序运行时间的因素
机器的速度（假设完全一样）
算法的好坏
输入数据规模
运行时间 = 执行次数 * 每次执行所需的时间。
由于每次执行所需的时间必须考虑到机器和编译程序的功能，因此通常只考虑执行的次数而已。
例如：
x=x+1; for (i=1; i <= n; i++) for(i=1; i<=n; i++)
x=x+1; for(j=1; j<=n; j++)
x=x+1;
1次 n次 n2次
4
程序运行时间
#2022
5
数组
int sum(int arr[ ], int n)
{
int i, total=0;
for (i=0; i < n; i++)
total += arr[i];
return total;
}
执行次数
1
n+1
n
1
________
2n+3
6
矩阵相加
假设两矩阵a, b皆为n*n。
void add(int a[ ][ ], int b[ ][ ], int c[ ][ ], int n)
{
int i, j;
for(i=0; i<n; i++)
for (j=0; j<n; j++)
c[i][j] =a[i][j]+b[i][j];
}
执行次数
1
n+1
n(n+1)
n2
________
2n2+2n+2
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;
}
}
7
矩阵相乘
执行次数
1
n+1
n(n+1)
n2
n2(n+1)
n3
n2
___________
2n3+4n2+2n+2
算法的渐近时间复杂度
单击此处添加正文，文字是您思想的提炼，为了演示发布的良好效果，请言简意赅地阐述您的观点。您的内容已经简明扼要，字字珠玑，但信息却千丝万缕、错综复杂，需要用更多的文字来表述；但请您尽可能提炼思想的精髓，否则容易造成观者的阅读压力，适得其反。
我们不需要进行如此精确的分析，究其原因：
算法中，进行精确分析是非常复杂的。 多数时候我们并不关心F(n)的精确度量，而只是关心其量级。
9
Big-O
算完执行次数后，通常利用Big-O来表示此算法的运行时间，如O(n)，亦称为该程序的「时间复杂度(time complexity)」。
Big-O取执行次数中最高次方或最大指数部份的项目即可。 如：
阵列元素相加为2n+3 = O(n)
矩阵相加为2n2+2n+1 = O(n2)
矩阵相乘为2n3+4n2+2n+2 = O(n3)
运用时间复杂度的观念，我们可以判断该程序的执行效率是否良好。
10
复杂度量级
O(1)：常数时间(constant time) 运行时间为常量
O(logn)：次线性时间(sub-linear)二分搜索算法
O(n)：线性时间(linear) n个数内找最大值
O(nlogn)快速排序算法
O(n2)：平方时间(quadratic) 选择排序，冒泡排序
O(n3)：立方时间(cubic)两个n阶矩阵的乘法运算
O(2n)：指数时间(exponential) n个元素集合的所有子集的算法
O(n!)：阶乘时间(factorial) N个元素的全排列的算法
如果n很大时 →
1< log n < n < n log n < n2 < n3 < 2n < n!
优<---------------------------<劣