共计 1466 个字符，预计需要花费 4 分钟才能阅读完成。
COMP352 Data Structures and Algorithms[数据结构与算法]是计算机专业的一门外围课程，3 学分，前置课程为 COMP232 和 COMP249。
本门课程讲授了一些根本的数据结构，如：栈，队列，链表，哈希表，对，二叉树，AVL 树，图等。难度比国内大学 简略得多。本专栏旨在对课程内容进行梳理与回顾。
如何评估效率？
办法的正确性仅仅取决于算法是否执行它应该做的事件。显然，效率不同于正确性。
效率能够用多种形式掂量，如：
- 内存利用率更低
- 更快的执行工夫
- 更快地开释调配的资源等
如何掂量效率？
- 测量应独立于应用的软件 (编译器 / 语言等) 和硬件(CPU 速度 / 内存大小等）
- 特地地，在程序运行时运行时剖析可能有重大的弱点
试验钻研
1) 编写一个实现该算法的程序；
2) 将不同数量的数据输出运行程序；
3) 应用相似 System.currentTimeMills() 的办法精确测量理论运行状况工夫；
4) 将后果描点作图进行剖析。
试验的局限性
1) 有必要实现该算法，这可能艰难 / 低廉；
2) 后果可能不示意试验中未蕴含的其余输出上的运行工夫；
3) 为了比拟两种算法，必须应用雷同的硬件和软件环境；
4) 在一些多道程序设计环境中，例如 Windows，很难确定一个工作须要多长时间。
如何评估效率？
效率在很大水平上取决于办法被如何定义。而对办法定义的的形象剖析是一种能够间接执行的钻研一种，因而成为首选。
疏忽各种限度，如：
- CPU 速度
- 内存限度；例如，容许 int 变量取任何容许的整数值，并容许数组取任意长度等。
因为当初的 办法 与特定的计算机环境无关，咱们称之为 算法。
预计运行工夫
如何依据算法的定义预计其运行 / 执行工夫？
咱们能够思考在算法中执行的语句数作为运行工夫的度量。这个度量能够示意为 问题规模 的函数。算法的运行工夫通常随着问题规模的增大而增大。
咱们个别关注最坏的状况，这对游戏、金融、机器人技术等应用程序至关重要。
给出一个规模为 n 的，找出worstTime(n)，它是一次执行中执行语句的最大数目。咱们要思考所有可能的参数 / 输出值。
例 – 1：假如有一个数组 a[0 … n]，思考以下程序：
for (int i= 0; i<n - 1; i++)
if (a[i] >a[i +1])
System.out.println (i);
worstTime(n)是多少？
所以，worstTime(n)是：4n-2.
伪代码
一种算法的高级形容，比英语散文更有条理，不如程序具体，是形容程序设计问题的算法的首选符号，暗藏程序设计的细节。
例 – 2：找出一个数组的最大元素
Algorithm arrayMax(A, n)
Input array A of n integers
Output maximun element of A
currentMax ← A[0]
for i ← 1 to n-1 do
if A[i]>currentMax then
currentMax ← A[i]
return currentMax
流程管制
if ... then ... [else ...]
while ... do ...
repeat ... until ...
for ... do ...函数申明
Algorithm method (arg [,arg...]
Input ...
Output ...函数调用
var.method(arg[,arg...])返回值
return expression表达式
← 赋值，相当于 java 中的 =
= 检测相等，相当于 java 中的 ==7 个重要的函数
在算法剖析中经常出现的 7 个函数
常数函数 = 1
对数函数 = log n
线性函数 = n
N-Log- N 函数 = nlog n
二次函数 = n^2
三次函数 = n^3
指数函数 = 2^n
