算法时空 第一周 基础部分

算法与计算

  • 计算:处理人类所不能处理的一些工作(难题),个人理解就是一些复杂性的难题,人类处理起来十分繁杂,计算机相比较容易,而且稳定性准确性更好。
  • 算法:输入->计算步骤->输出

排序问题:

  • 输入:n 个键值 (a1, a2,…,an)
  • 输出:升序输出
  • 例子:y, x, z -> x, y, z 。 按照字母顺序输出
  • 约束:序关系

优秀的算法:

  • 正确->思路清晰
  • 高效->算法分析
  • 易于实现->现成的算法

停机问题:是指算法能正确的停止下来 3n+1问题:有一个整数,如果是偶数就除以二,如果是奇数就是乘以3再加一,结果依次计算下去,看最后能不能变成1

算法的用处:

  • 生物信息学
  • 网络:图论, 字符串查找
  • 信息安全: RSA
  • 优化:调度

算法问题

  • 图论:最短路径
  • LCS: DP(动态规划)
  • 拓扑排序
  • 凸包

数据结构

速度差异