算法红皮书 1.4.1-1.4.10

算法分析 #

使用数学分析为算法成本建立简洁的模型，并使用实验数据验证这些模型

科学方法 #

观察、假设、预测、观察并核实预测、反复确认预测和观察
原则：实验可重现

观察 #

计算性任务的困难程度可以用问题的规模来衡量
问题规模可以是输入的大小或某个命令行参数的值
研究问题规模和运行时间的关系

使用计时器得到大概的运行时间 ly-20241212142054451

典型用例

public static void main(String[] args) {
        int N = Integer.parseInt(args[0]);
        int[] a = new int[N];
        for (int i = 0; i < N; i++)
            a[i] = StdRandom.uniform(-1000000, 1000000);
        Stopwatch timer = new Stopwatch();
        int cnt = ThreeSum.count(a);
        double time = timer.elapsedTime();
        StdOut.println(cnt + " triples " + time + " seconds");
    }

使用方法

数据类型的实现

public class Stopwatch {
    private final long start;

    public Stopwatch() {
        start = System.currentTimeMillis();
    }

    public double elapsedTime() {
        long now = System.currentTimeMillis();

        return (now - start) / 1000.0;
    }
}

数学模型 #

程序运行的总时间主要和两点有关：执行每条语句的耗时；执行每条语句的频率
定义：我们用~f(N) 表示所有随着N 的增大除以f(N) 的结果趋近于1 的函数。我们用g(N) ~ f(N) 表示g(N)/f(N) 随着N 的增大趋近于1。即使用曰等号忽略较小的项
$$ f(N)=N^b(logN)^c $$
将f(N)称为g(N)的增长的数量级
常见的增长数量级函数
本书用性质表示需要用实验验证的猜想
- ThreeSum分析执行最频繁的指令决定了程序执行的总时间–我们将这些指令称为程序的内循环
- 程序运行时间的分析
- 算法的分析 ThreeSum的运行时间增长数量级为N^3，与在哪台机器无关
- 成本模型 3-sum的成本模型：数组的访问次数（访问数组元素的次数，无论读写）
- 总结-得到运行时间的数学模型所需的步骤
  - 确定输入模型，定义问题的规模
  - 识别内循环
  - 根据内循环中的操作确定成本模型
  - 对于给定的输入，判断这些操作的执行效率

增长数量级的分类 #

成长增长的数量级一般都是问题规模N的若干函数之一，如下表
- 常数级别表示运行时间不依赖于N
- 对数级别，经典例子是二分查找
- 线性级别（常见的for循环）
- 线性对数级别，其中，对数的底数和增长的数量级无关
- 平方级别，一般指两个嵌套的for循环
- 立方级别，一般含有三个嵌套的for循环
- 指数级别
问题规模（图）
典型的增长数量级函数（图）
典型的增长数量级函数
在某个成本模型下可以提出精确的命题比如，归并排序所需的比较次数在$1/2NlgN$~$NlgN$之间，即归并排序所需的运行时间的增长数量级是线性对数的，也就是：归并排序是线性对数的

设计更快的算法 #

前提，目前已知归并排序是线性对数级别的，二分查找是对数级别的

将3-sum问题简化为2-sum问题，即找出一个输入文件中所有和为0的整数对的数量，为了简化问题，题设所有整数均不相同

可以使用双层循环，以平方级别来解决
改进后的算法，当且仅当-a[i]存在于数组中且a[i]非零时，a[i]存在于某个和为0的整数对之中

代码如下

import java.util.Arrays;

	public class TwoSumFast {
		public static int count(int[] a) { // 计算和为0的整数对的数目
			Arrays.sort(a);
			int N = a.length;
			int cnt = 0;
			for (int i = 0; i < N; i++)
				if (BinarySearch.rank(-a[i], a) > i)
					cnt++;
			return cnt;
		}

		public static void main(String[] args) {
			int[] a = In.readInts(args[0]);
			StdOut.println(count(a));
		}
	}

3-sum问题的快速算法

当且仅当-(a[i]+a[j])在数组中,且不是a[i]也不是a[j]时，整数对(a[i]和a[j])为某个和为0的三元组的一部分
总运行时间和$N^2logN$成正比

代码如下

import java.util.Arrays;


public class ThreeSumFast {
    public static int count(int[] a) { // 计算和为０的三元组的数目
        Arrays.sort(a);

        int N = a.length;
        int cnt = 0;

        for (int i = 0; i < N; i++)
            for (int j = i + 1; j < N; j++)
                if (BinarySearch.rank(-a[i] - a[j], a) > j) {
                    cnt++;
                }

        return cnt;
    }

    public static void main(String[] args) {
        int[] a = In.readInts(args[0]);
        StdOut.println(count(a));
    }
}

下界
- 为算法在最坏情况下的运行时间给出一个下界的思想是非常有意义的
- 运行时间的总结
  图1 图2
- 实现并分析该问题的一种简单解法，我们称之为暴力算法
- 算法的改进，能降低算法所需的运行时间的增长数量级

倍率实验 #

翻倍后运行时间，与没翻倍时的运行时间成正比

代码

public class DoublingRatio
{
	public static double timeTrial(int N)
		// 参见DoublingTest（请见1.4.2.3 节实验程序）
	public static void main(String[] args)
		{
		double prev = timeTrial(125);
		for (int N = 250; true; N += N)
				{
			double time = timeTrial(N);
			StdOut.printf("%6d %7.1f ", N, time);
			StdOut.printf("%5.1fn", time/prev);
			prev = time;
		}
	}
}

试验结果
预测
倍率定理（没看懂，不管）
- 评估它解决大型问题的可行性
- 评估使用更快的计算机所产生的价值

注意事项 #

大常数，$c = 10^3或106$
非决定性的内循环
指令时间
系统因素
不分伯仲（相同任务在不同场景效率不一样）
对输入的强烈依赖
多个问题参量

处理对于输入的依赖 #

输入模型，例如假设ThreeSum的所有输入均为随机int值，可能不切实际
输入的分析，需要数学几千
对最坏情况下的性能保证
- 命题（这里只针对之前的代码）
对计划算法，有时候对输入需要进行打乱
操作序列
均摊分析通过记录所有操作的总成本并除以操作总数来将成本均摊

内存 #

Java的内存分配系统
原始数据类型的常见内存、需求这里漏了，short也是2字节。总结boolean、byte 1字节；char、short 2字节；int、float 4字节；long、double 8字节
对象（跳过）
- 要知道一个对象所使用的内存量，需要将所有实例变量使用的内存与内存本身的开销（一般是16字节）
- 一般内存的使用都会被填充为8字节的倍数（注意，说的是64位计算机中的机器字）
- 引用存储需要8字节
- 典型对象的内存需求例如第一个，16+4=20；20+4 = 24为8的倍数
- 链表，嵌套的非静态（内部）类，如上面的Node，需要额外的8字节（用于外部类的引用）
- 数组 int值、double值、对象和数组的数组对内存的典型需求比如一个原始数据类型的数组，需要24字节的头信息（16字节的对象开销，4字节用于保存长度[数组长度]，以及4填充字节，再加上保存值需要的内存） Date对象需要的：一个含有N 个Date 对象（请见表1.2.12）的数组需要使用24 字节（数组开销）加上8N 字节（所有引用）加上每个对象的32 字节，总共（24 +40N）字节【这里说的是需要，和本身存储是两回事】

![ly-20241212142056395](img/ly-20241212142056395.png)

字符串对象
String 的标准实现含有4 个实例变量：一个指向字符数组的引用（8 字节）和三个int 值（各4 字节）。第一个int 值描述的是字符数组中的偏移量，第二个int 值是一个计数器（字符串的长度）。按照图1.4.10 中所示的实例变量名，对象所表示的字符串由value[offset]到value[offset + count - 1] 中的字符组成。String 对象中的第三个int 值是一个散列值，它在某些情况下可以节省一些计算，我们现在可以忽略它。因此，每个String 对象总共会使用40字节（16 字节表示对象，三个int 实例变量各需4 字节，加上数组引用的8 字节和4 个填充字节）
字符串的值和子字符串
- 一个长度为N 的String 对象一般需要使用40 字节（String 对象本身）加上（24+2N）字节（字符数组），总共（64+2N）字节
- Java 对字符串的表示希望能够避免复制字符串中的字符
- 一个子字符串所需的额外内存是一个常数，构造一个子字符串所需的时间也是常数
- 关于子字符串

展望 #

最重要的是代码正确，其次才是性能