【Day1】资料结构 + 演算法

程序设计中资料结构与演算法是非常重要的两大项目，彼此之间都会影响程序的运作。

资料结构

电脑在储存资料时，会储存在电脑的记忆体中，而资料可以有不同的储存与组织方式，即为资料结构。

最佳化的资料结构是能在有限的记忆体中，有组织地控制资料存放的位置或顺序，并且配合适当演算法，来有效地提高运算速度。换句话说，选择适当的资料结构能够提高演算法的效率。

可以想像水跟书是不同种的结构，杯子与书柜各适合放入什麽样的结构?水倒入杯子比较方便测量，书放上书柜比较方便排序。

不同种的资料结构适合不同的应用，一位程序设计师必须选择一种资料结构来进行资料的新增、删除、修改…等动作，若在选择资料结构时作了错误决定，将造成程序执行上变得没效率。

演算法

演算法被定义为一个可以用来解决某一问题的方法或算法。可以想像一份料理食谱，里面写着做成这份料理的步骤，这样的概念套用到电脑领域，用特定方法来解决特定问题，就是演算法的诞生。

这样的过程，可以用下图来表示:

现代生活中，你的周遭就有许多演算法，像是Facebook会根据你的好友关系，给予推荐的好友;Spotify会根据你常听的音乐类型，给予推荐的歌曲;Youtube会根据你常看的影片类型或频道，给予相关推播;甚至我们平时常用的搜寻引擎也必须藉由不断更新演算法来运作。

Donald Ervin Knuth提出了演算法必须具备的五个特性:

1. 输入(Input):0个或是1以上的输入。
2. 输出(Output):至少有一个输出结果。
3. 明确性(Definiteness):每个步骤或指令必须是明确的而不含糊的。
4. 有限性(Finiteness):在有限的步骤後一定会结束，不会有无穷回圈。
5. 有效性(Effectiveness):每个步骤清楚具有可行性，能用纸笔来表达。

复杂度

复杂度可以用来衡量演算法的效率，又分为时间复杂度(Time Complexity)与空间复杂度(Space Complexity)，通常会用Big O来表示。

关於时间复杂度(Time Complexity)

可以说电脑执行演算法所花费的时间成本。花费的时间并非以秒为单位计算，是以执行的次数来做计算。

关於空间复杂度(Space Complexity)

可以说是电脑执行演算法所需要耗费的记忆体空间。

而时间复杂度和空间复杂度两者是可以互相trade off的。

Trade off意思是在某些情况下，我们是可以让程序多用一些记忆体空间记下一些会被重复使用的资讯，能够省去一些重复的运算，来加速程序的执行时间；或者我们完全没有多余的记忆体资源可以使用，可以透过把一些原本可以靠记忆体储存的资讯改用重复计算的方式来取得。也就是一种用空间来换取时间，用时间换取空间的概念。

常见的Big O又分为下面几种

• O(1):常数时间，不管你输入多少资料，执行时间不变。
• O(n):线性时间，执行时间会随着输入多少资料 n 等比例增加。
• O(n²):平方时间，执行时间会成二次方成长。
• O(2^n):指数时间，执行时间会成2的n次方成长，效能较差，尽可能避免。
• O(log n):对数时间，log 8 = 3，也就是8 = 2³，执行时间一开始增加，到一定程度後无明显增加。
• O(n log n):线性对数时间，介於线性与平方之间。