算法-基础

概览： 程序结构、数据类型、复杂度分析和增长数量级

基础编程模型

语言特性、软件库和操作系统特性总称之为基础编程模型。

Java程序基本结构

  1. 原始数据类型
  2. 语句
  3. 数组
  4. 静态方法
  5. 字符串
  6. 标准输入、输出
  7. 数据抽象（对象）

原始数据类型与表达式

  1. 整型 int 4字节 范围 2^32-1 , -2^31~2^31-1
  2. 浮点型 double 双精度实数 8字节 2^64-1
  3. 布尔型 boolean 1字节 2^8-1
  4. 字符型 char 2字节 2^16
  5. long 8字节 64位整数
  6. short 2字节 16位整数
  7. byte 1字节 8位整数
  8. float 4字节 32位单精度实数。

实数使用浮点表示法，IEEE定义了几种存储浮点数的标准。
单精度32其中，1位符号8位指数23位尾数，余127码
双精度64，1符号，11位指数，52位尾数

语句：

  1. 声明语句
  2. 赋值语句
  3. 条件语句
  4. 循环语句
  5. 调用和返回

方法的性质：

  1. 方法的参数按值传递
  2. 方法名可以被重载
  3. 方法只能返回一个值
  4. 方法可以产生副作用

递归：

  1. 递归总有一个最简单情况
  2. 递归调用收敛到最简单的情况
  3. 递归调用的父问题和尝试解决的子问题不应有交集。

数据抽象

数据类型指一组值和一组对这些值的操作的集合。
抽象数据类型是一种对使用者隐藏数据表示的数据类型

对象三大特性：状态、标识、行为。
创建对象：

  1. 为新对象分配内存空间
  2. 调用构造函数初始化对象的值
  3. 返回该对象的一个引用

== 和 equals
== 比较的是引用是否相同
equals比较对象的散列值hashCode是否相同

算法分析

程序在不同计算机上的运行时间之比通常是一个常数。

对数图像中的直线等价于我们对数据符合公式的T(N)=aN^b猜想，这种公式称为幂次法则。我们假设程序的运行时间复核幂次法则。对于算法分析，我们有许多数学模型。

数学模型

一个程序运行的总时间和两点有关：

  1. 执行每条语句的耗时；
  2. 执行每条语句的频率；

近似：
使用~略去数值小的项来简化表达式。
一般我们用到的近视方程都是g(N)~af(N),其中f(N)=N^b*(logN)^c,其中a，b，c均为常数。我们将f(N)成为g(N)的增长的数量级。

常见的增长数量级函数：

描述 增长的数量级 说明 举例
常数级别 1 普通语句 两数相加
对数级别 logN 二分策略 二分查找
线性级别 N 循环 找出最大元素
线性对数级别 NlogN 分治 归并排序
平方级别 N^2 双层循环 检查所有元素对
立方级别 N^3 三层玄幻 检查所有三元组
指数级别 2^N 穷举查找 检查所有子集

近似运行时间：
假设每个java代码块所对应机器指令所需执行时间都是固定的。
执行最频繁的指令决定了程序执行的总时间–内循环。

算法的分析：
增长数量级函数概念将程序和它实现的算法隔离开来。使用的算法决定了增长的数量级。

成本模型：
使用成本模型评估算法的性质。如访问数组元素的次数。我们希望通过明确成本模型使给定实现所需的运行时间的增长数量级和它背后的算法的成本的增长数量级相同（成本模型应该和内循环中的操作相关）

得到程序运行时间的数学模型所需步骤如下：

  1. 确定输入模型，定义问题的规模；
  2. 识别内循环；
  3. 根据内循环中的操作确定成本模型；
  4. 对于给定的输入，判断这些操作的执行频率；

如：二分查找

  1. 输入模型是大小为N的数组 a[]；
  2. 内循环是一个while循环中的所有语句；
  3. 成本模型是比较操作；
  4. 它所需的比较次数做多为lgN+1

增长数量级的分类

  1. 常数级别：完成任务所需操作数一定，运行时间不依赖N（问题规模）
  2. 对数级别：运行时间的增长数量级为对数的程序仅比常数时间的程序稍慢。对数的底数和增长的数量级无关（因为不同的底数相当于一个常数因子）。
  3. 线性级别：运行时间和N成正比。如单个for循环
  4. 线性对数级别：对数的底数和增长的数量级无关。如归并排序、快速排序。
  5. 平方级别：如两个嵌套for循环、选择排序、插入排序
  6. 立方级别
  7. 指数级别：用来描述增长数量级为b^N的算法。

注意事项

分析程序性能时，得到不一致或误导性结果原因有多种。

  1. 大常数
  2. 非决定性的内循环
  3. 指令时间
  4. 系统因素
  5. 不分伯仲
  6. 对输入的强烈依赖
  7. 多个问题参量

阅读进度：
共648 15~622 = 607 14天
3天 15~148 = 133 44 p/t
11.06 - 11.22 算法·第四版

动态连通性

假设相连是一种对等的关系，能够将对象分为多个等价类。当且仅当两个对象相连时它们才属于同一个等价类。
目标是编写程序过滤序列中所有无意义的整数对。

抽象：
将输入的所有整数看作属于不同的数学合集。在处理整数对pq时，判断是否属于相同的集合。若不是，会将p所属集合和q所属集合归并，最终所有整数属于同一个集合。
将对象称为触点，将整数对称为连接，将等价类成为联通分量或分量。

推荐文章