算法练习(57): TwoSum分析(1.4.4)

本系列博客习题来自《算法(第四版)》，算是本人的读书笔记，如果有人在读这本书的，欢迎大家多多交流。为了方便讨论，本人新建了一个微信群(算法交流)，想要加入的，请添加我的微信号：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壁纸宝贝上线了，欢迎大家下载。