老男孩IT教育,只培养技术精英

全国免费咨询电话:400-609-2893
JAVA中算法丨时间频度与时间复杂度

    /    2018-08-06

时间频度

时间复杂度通常是衡量算法的优劣的,衡量算法的时间严格来讲是很难衡量的,由于不同的机器性能不用环境都会造成不同的执行时间。

算法的执行时间和语句的执行次数成正比,因此通过计算执行测试来推断执行时间。算法中语句执行次数称为语句频度或时间频度,记为T(n),n是问题的规模,T是Time,即时间频度。

时间复杂度

n不断变化时,T(n)也在不断变化,为了考察两者变化时呈现什么规律,可以使用时间复杂度来计算。

通常操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),存在一个正常数c使得f(n) * c >= T(n)恒成立。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。

简言之,只要计算一下语句的执行次数和n之间的关就可以了,去除系数部分,低阶项目部分,就是时间复杂度的值了。

时间复杂度的计算

给定任意长度数组,读取数组第一个元素的值

无论数组长度n为多少,代码执行一次。因此,时间复杂度为O(1)。

循环n次,输出hello world

随着n的增大,打印函数逐渐增多。打印代码执行的次数是n,因此时间复杂度为O(n)。

打印99乘法表

打印99正方乘法表,打印语句输出9 * 9 = 81次。

打印正三角的99乘法表

正三角形状的99表格打印语句的执行次数为:

冒泡排序

冒泡排序是经典的排序算法是每次比较相邻的两个元素进行对调,进行多轮,知道数列有序。

对于5个元素的冒泡排序来说,共需要比较4 + 3 + 2 + 1次比较。因此时间复杂度为:

冒泡排序可以进行优化,在最好的情况下,复杂度为O(n),思路如下:

设置标志位flag=1,表示整个数列已经有序,就不需要再排序了,在里层循环中,如果发现没有进行过数据交换,就所说数列已经有序。

在最好情况下,就是数列本身已经有序,只需要执行外层的n-1次循环即可,因此复杂度为O(n)。

折半查找

折半查找也叫二分查找,是高效的查找方式,前提条件是数列需要时有序数列。图例如下:

代码如下:

折半查找的最坏时间复杂度为:

以2为底,n的对数。

O(log_2 n )

hashmap

hasmap是java中最重要的集合之一,设计非常巧妙,使用通过数组+链表方式组合实现,哈希的目的是让对象在空间内尽可能分散。

那么HashMap的时间复杂度是多少呢?

矩阵的乘积

矩阵我们按照阶数为n的两个方阵进行计算,矩阵的乘法运算法则为:

方阵乘法的代码如下:

(0)

分享至