工作一段快两年了,感觉之前学的数据结构和算法基本忘得差不多了,最近一段时间准备复习一下相关知识。
有一个求数组中最大和最小数的题目,基本的思路是遍历一遍数组,然后每个一个元素都和最大值和最小值比较,时间复杂度是2(N-1)或2N。
比较简单的一种减少复杂度的方法是把数组的元素两两分组比较,然后较大的数和max比较,较小的数和min比较,这种实现方法的时间复杂度是1.5N。
还有一种是采用分治法,比较次数也是1.5N,思路是将数组一分为二,分别获取两个子数组的最大和最小值,然后进行取两个子数组中较小的最小值和较大的最大值。
O(N) = (N/2 + N/4 + … + N/2^(log2(N))) = 3N/2 (收敛?)