《算法导论》之2021SPR《算法分析与设计》笔记
第一章 算法在计算中的作用 习题 1.2-2 假设我们正比较插入排序与归并排序在相同机器上的实现。对规模为n的输入，插入排序运行8n^2步，而归并排序运行64nlgn步。问对哪些n值，插入排序优于归并排序? 解： 建立不等式：8n^2 < 64nlog_2n 化简：n < 8log_2n 取不等式的正整数解，即n = 2, 3, ... , 43时，插入排序由于归并排序。 第二章 算法基础 插入排 ...
第一章 算法在计算中的作用 习题 1.2-2 假设我们正比较插入排序与归并排序在相同机器上的实现。对规模为n的输入，插入排序运行8n^2步，而归并排序运行64nlgn步。问对哪些n值，插入排序优于归并排序? 解： 建立不等式：8n^2 < 64nlog_2n 化简：n < 8log_2n 取不等式的正整数解，即n = 2, 3, ... , 43时，插入排序由于归并排序。 第二章 算法基础 插入排 ...