Home

LinkWorld Algorithm Blog

15 Sep 2019

算法基础

前言

大学没有开算法课程,还是要自己学学。

算法的特征

  • 有穷性
    • 算法执行到有穷步之后必须终止。
  • 确定性
    • 算法的每一步骤必须有确切的定义。要执行的每一个动作都是清晰的、无歧义的。欧几里德算法规定了m和n都是正整数,从而保证了算法能够确定地执行。
  • 输入
    • 一个算法有0个或多个输入,作为算法开始执行前的初始值,或初始状态。所谓0个输入是指算法本身定出了初始条件。
  • 输出
    • 一个算法有一个或多个输出,以反映对输入数据加工后的结果。没有输出的算法是毫无意义的。
  • 可行性
    • 在有限时间内完成计算过程。

算法的复杂性

  一般把时间复杂性和空间复杂性分开,并分别用$T$和$S$来表示:算法的时间复杂性一般表示为$T(n)$;算法的空间复杂性一般表示为$S(n)$。其中$n$是问题的规模(输入大小)。

  算法的时间复杂性(Time Complexity)是指执行算法所需要的时间。 一般来说,计算机算法是问题规模n的函数f(n),算法的时间复杂性也因此记做$T(n)=O(f(n))$,问题的规模$n$越大,算法执行的时间的增长率与$f(n)$的增长率正相关,称作渐进时间复杂性(Asymptotic Time Complexity)。

  算法的空间复杂性(Space Complexity)是指算法需要消耗的内存空间。

空间复杂度分析 说明
静态分析 一个算法静态使用的存储空间,称为静态空间。 静态分析的方法比较容易,只要求出算法中使用的所有变量的空间,再折合成多少空间存储单位即可。
动态分析。 一个算法在执行过程中,必须以动态方式分配的存储空间是指在算法执行过程中分配的空间,称为动态空间。 动态空间主要是存储中间结果或操作单元所占用空间。

国内主要的几个在线测试题库

学校 网址
浙江大学(ZJU) http://acm.zju.edu.cn
北京大学(PKU) http://poj.org
杭州电子科技大学(HDU) http://acm.hdu.edu.cn
浙江工业大学(ZJUT) http://acm.zjut.edu.cn

国外的几个在线测试题库

学校 网址
俄罗斯乌拉尔大学(URAL) http://acm.timus.ru
俄罗斯萨拉托夫大学(SGU) http://acm.sgu.ru
西班牙瓦拉杜利德大学(UVA) http://acm.uva.es
美国USACO http://train.usaco.org/usacogate

Til next time,
LinkWorld at 17:18

scribble