有句话是 「programming = data structures + algorithms」,一个好的程序码需要好的资料结构与演算法,而演算法最看重的就是复杂度,复杂度越小,程序码就越有效率。
简而言之,演算法是用来解决问题的,而最常见的做法就是将一个大问题分解成好多个小问题,并解决这些子问题,而这样的方式称作递回 (recursion)。
此外,演算法中强调了两种复杂度,分别为空间复杂度(space complexity)与时间复杂度(time complexity),在大部分的情况,时间复杂度比空间复杂度来得更重要。
我们最常见的递回做法就是写一个函数并不断重复使用。
在河内塔(Hanoi tower)的例子中,应用递回是一个非常 clever 的做法,不过,并不是万灵丹,相信大家对Fibonacci数列都不陌生,就是 1, 1, 2, 3, 5, 8, 13, 21,...,从第三个数开始,每一项都是前两项的和,我们可以分别比较 recursion、repetitive 的做法:
Recursion
fib(n-1) + fib(n-2)
Repetitive
int fib1 = 1, fib2 = 1;
for (int i = 2; i < n; i++) {
fib3 = fib1 + fib2
fib1 = fib2
fib2 = fib3
}
在这样的情况下,选择 repetitive 的做法会比 recursion 来得更好,因为 repetitive 会花费的时间是 polynomial time,也就是说其所需要跑 次 (C1为ㄧ定值),而 recursive 则是算 exponential time,也就是他会跑 次(C2为一定值)。因此,当 n 大到一定程度时, 会大於 。
Search 是一个非常常见的递回应用。
假设我们现在有一个阵列A以及一整数 p,我们想要知道 p 是否在於A,而且这个阵列 A 是没有排序过的阵列,一个最直观的方法就是 linear search,就是从A的第一项开始判断,从头开始一个一个的找,这个方法简单明了,不过呢,有的时候可能会有点没效率,如果今天我们这个阵列是已经排序好了,使用 binary search 可能更好。
Binary search
首先,我们先跟中位数 m 做比较,这时候我们有三种情况:
接着我们可以写一个函数
binarySearch (a sorted array A, search in between from and to, search for p)
if n = 1
return true if Afrom = p; return false otherwise
else
let median be floor((from + to) / 2)
if p = Amedian
return true
else if p < Amedian
return binarySearch(A, from, median, p)
else
return binarySearch(A, median + 1, to, p)
Binary search 可以让我们的效率大幅提升,我们只需要跑 次!
有两种sorting的方式:insertion sort & merge sort。
Insertion sort
insertionSort(a non-repetitive array A, the array length n, an index cutoff < n)
// at any time, A1..cutoff is sorted and A(cutoff + 1)..n is unsorted
if Acutoff + 1 < A1..cutoff
let p be 1
else
find p such that Ap – 1 < Acutoff + 1 < Ap
insert Acutoff + 1 to Ap
and shift Ap..cutoff to A(p + 1)..(cutoff + 1)
if cutoff + 1 < n
insertionSort(A, n, cutoff + 1)
Merge sort
Merge sort 就是将一个排列好的阵列插入另一个排列好的阵列。
首先要先开一个跟总数一样大的阵列,接下来:
mergeSort(an array A, the array length n)
let median be floor((1 + n) / 2)
mergeSort(A1..median, median)
// now A1..median is sorted
mergeSort(A(median + 1)..n, n – median + 1)
// now A(median + 1)..n is sorted
merge A1..median and A(median + 1)..n
以上就是今天的内容!
>>: Day 29 - Rancher Fleet Helm + Kustomize 应用程序部署
本文介绍 Projucer 的基本用法,後续还有一些使用经验分享。 JUCE 是一跨平台开发框架(F...
本篇文章同步发表在 HKT 线上教室 部落格,线上影音教学课程已上架至 Udemy 和 Youtu...
在 什麽是 JSX (Day2) 的时候有写过,JSX 会经过 Bable 转译成 React.cr...
基本语法 就让我们从大家学程序语言第一个程序码「Hello world!」开始讲起吧! #inclu...
接下来要这篇文章要来谈谈很常听到的『 Active Record 』。 什麽是 Active Rec...