本系列博客习题来自《算法(第四版)》，算是本人的读书笔记，如果有人在读这本书的，欢迎大家多多交流。为了方便讨论，本人新建了一个微信群(算法交流)，想要加入的，请添加我的微信号：zhujinhui207407 谢谢。另外，本人的个人博客 http://www.kyson.cn 也在不停的更新中，欢迎一起讨论
算法(第4版)
知识点
- TwoSum
- 画图
题目
1.4.4 参照表 1.4.4 为 TwoSum 建立一张类似的表格。
1.4.4 Develop a table like the one on page 181 for TwoSum.
分析
参照中英文的翻译，看看，181页对应的图表是如图所示的图表
参照3-sum不难得出2-sum的代码如下：
public class TwoSum
{
public static int count(int[] a)
{
int N = a.length;
int cnt = 0;
for (int i = 0; i < N; i++)
for(int j = i + 1; j < N; j++)
if(a[i] + a[j] == 0)
cnt++;
return cnt;
}
public static void main(String[] args)
{
int[] a = In.readInts(args[0]);
StdOut.println(count(a));
}
}
因此画出如下语句执行频率图：
Anatomy of a program’s statement execution frequencies
对应的程序运行的时间分析表：
| statement block | time in seconds | frequency | total time |
|---|---|---|---|
| D | t₀ | x (depends on input) | t₀x |
| C | t₁ | N²/2-N/2 | t₁( N²/2-N/2 ) |
| B | t₂ | N | t₂N |
| A | t₃ | 1 | t₃ |
广告
我的首款个人开发的APP壁纸宝贝上线了，欢迎大家下载。
