数据结构-算法分析

算法是什么

答案顾名思义,有着一些指示用来解决问题的就是算法。 程序只是用来将算法表达出来。

如何量度算法的表现?

四点: 1. 程序代码的长度 2. 程序的维护工作 3. 容量空间的要求 4. 运行时间 其方法:时间复杂度) Time of Complexity(时间复杂度): 我们运用到4中非对称表达式:

1
2
3
4
5
6
7
8
1\. Big-O —>(T(n) = O(f(n))
T(n) <= c*f(n) —>’Bounded above by’ (渐进上界)
2\. Big-Omega —>(T(n) = Omega(f(n)))
T(n) >= c *f(n) —>”bounded below by” (渐进下界)
3\. Big-Theta
T(n) = c *f(n) —>”bounded below and above by”
4\. Big-littleo —-> T(n)< c f(n)
T(n)/p(n) ->0 as n —>无限大 (严格下界)

通常Big-O在数据结构中用的最多,因为我们需要量度算法的下界,也就是worst case, Big-Omega较少用到,毕竟很难量度最好表现 数据结构的一些会用到的公式(Useful rules of data structure):

1
2
3
4
5
Rule 1: 加法法则(rule of sum)
T1(n) + T2(n) = O(max(T1(n), T2(n)))
Rule 2: 乘法法则(rule of product)
T1(n) * T2(n) = O(T1(n) * T2(n))
Rule 3: log^k n = O(n) 且 在任何k值的情况下(For any constant k) –> log的增长率十分慢(log grows very slowly)

一般情况下,时间复杂度是由许多部分组成,只需要找出最大的部分 除去其他部分(包括乘法因子) 普遍的复杂度(从小到大):

O(1) , O(log n), O(n), O(n log n), O(n^2), O(n^3), O(2^n), O(n!)

前面是介绍一些数据结构的定义和数学, 现在下面介绍的是正式的对算法的分析: 算法中, 既定的规则:

1.一些基本的语句(assign, read or write or +-/*==) 运行时间: constant O(1) 2. 循环语句一般看循环的次数

1
2
3
4
5
6

for(i = 0; i< n; i++){
if(a == n-1){
return 1;
}
} --->运行时间:O(n)

3.. Nested loops(嵌套循环)所有循环的次数size相乘

1
2
3
4
5
6
for (i=1; i<n-1; i++)  --> O(n)
for (j=n; j>= i+1; j--) --> O(n)
if (A(j-1) > A(j)) then
temp = A(j-1);
A(j-1) = A(j);
A(j) = tmp;

总运行时间: O(n^2) 4.. If/else 决策算法 根据所测试的部分来决定该算法的时间复杂度, 不过条件是constant O(1)

  • 版权声明: 本博客所有文章,未经许可,任何单位及个人不得做营利性使用!转载请标明出处!如有侵权请联系作者。
  • Copyrights © 2015-2020 翟天野

请我喝杯咖啡吧~