GuangchaoSun's Blog

1.4 Analysis of Alorithms

发表于  |    |   分类于   |  

本节你会了解到：

  • 各种数据结构在内存中所占空间的大小
  • 简单地了解一下复杂度

大多数情况下，得到运行时间的数学模型需要进行以下步骤：

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

对增长数量级的常见总结：

一般来说，二分策略的数量级为logN，比如二分查找；分治策略的数量级为NlogN，比如归并排序。

找到数组中三者和为零的个数
ThreeSumFast:

1
2
3
4
5
6
7
8
9
10
11
12
13
public static int count(int[] a)
{
    Array.sort(a);
    int N = a.length();
    itn cnt = 0;
    for(int i = 0;i < N;i++)
        for(int j = i+1;j < N;j++)
        {
            int k = Array.binarySearch(-a[i]-a[j],a);
            if(k > j) cnt++;
        }
        return cnt;
}

TwoSumFast:

1
2
3
4
5
6
7
8
9
10
11
public static int count(int[] a)
{
    int n = a.length;
    Array.sort(a);
    int count = 0;
    for(int i = 0;i < n; i++){
        int j = Array.binarySearch(a,-a[i]);
        if(j > i) count++;
    }
    return count;
}

2-sum问题的线性对数级别的解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class TwoSumFast{
    public static int count(int [] a)
    {
        Arrays.sort(a);
        int N = a.length();
        int cnt = 0;
        for(int i = 0;i < N;i++)
        {
            if (BinarySearch.rank(-a[i],a) > 0)
                cnt ++;
        }
        return cnt;
    }
    public static void main(String[] args){
        int[] a = In.readInts(args[0]);
        StdOut.println(count(a));
    }
}

3-sum问题的快速算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class ThreeSumFast{
	public static int count(int[] a)
	{
		Array.sort(a);
		int N = a.length();
		int cnt = 0;
		for(int i = 0;i < N;i++)
		{
			for(j = i+1;j < N;j++)
				if(BnarySearch.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));
	}
}

命题D：在Bag、Stack、Queue的链表实现中所有的操作在最坏情况下所需时间都是常数级别的。
在对程序进行性能分析时的注意事项：

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

内存

对象
一个Integer对象会使用24字节的空间，其中16字节的对象开销，4字节存储int值，还有4字节填充字节（padding）。
Integer memory

同理，一个Date对象使用32字节的空间。
Date momery

链表
一个内部类的话：16字节的对象开销+8字节的额外开销+指向item和next对象引用各需8字节 = 40byte

此处输入图片的描述

数组
Java中数组被实现为对象，数组的空间包括对象所需内存加上引用所需内存。

例如，一个含有N个Date对象的数组，需要使用24字节（数组开销，包括16字节的对象开销，4字节保存长度以及4填充字节）加上8N字节（所有对象的引用）加上每个Date对象的32字节，总共(24+40N)字节

字符串对象
一个String对象一般需要40字节（16字节表示对象，三个int实例变量：偏移量、计数器、散列值个需要4字节，加上数组引用8个字节和4个填充字节）。

Q + A

Q. How do I increase the amount of memory and stack space that Java allocates?

A. You can increase the amount of memory allotted to Java by executing with java -Xmx200m Hello where 200m means 200 megabytes. The default setting is typically 64MB. You can increase the amount of stack space allotted to Java by executing with java -Xss200k Hello where 200k means 200 kilobytes. The default setting is typically 128KB. It’s possible to increase both the amount of memory and stack space by executing with java -Xmx200m -Xss200k Hello.

Q. What is the purpose of padding(填充字节)?
A. Padding makes all abjects take space that is a mulitple of 8 bytes.This can waste some memory but it speeds up memory access and garbage collection(垃圾回收).

Creative Problems

14.4-sum.Develop a brute-force solution FourSum.java to the 4-sum problem.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
public class FourSum {
    // print distinct 4-tuples (i, j, k, l) such that a[i] + a[j] + a[k] + a[l] = 0
    public static int printAll(long[] a) {
        int N = a.length;
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            for (int j = i+1; j < N; j++) {
                for (int k = j+1; k < N; k++) {
                    for (int l = k+1; l < N; l++) {
                        if (a[i] + a[j] + a[k] + a[l] == 0) {
                            StdOut.println(a[i] + " " + a[j] + " " + a[k] + " " + a[l]);
                        }
                    }
                }
            }
        }
        return cnt;
    }
    // return number of distinct 4-tuples (i, j, k, l) such that a[i] + a[j] + a[k] + a[l] = 0
    public static int count(long[] a) {
        int N = a.length;
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            for (int j = i+1; j < N; j++) {
                for (int k = j+1; k < N; k++) {
                    for (int l = k+1; l < N; l++) {
                        if (a[i] + a[j] + a[k] + a[l] == 0) {
                            cnt++;
                        }
                    }
                }
            }
        }
        return cnt;
    }
    public static void main(String[] args)  {
        int N = StdIn.readInt();
        long[] a = new long[N];
        for (int i = 0; i < N; i++) {
            a[i] = StdIn.readLong();
        }
        int cnt = count(a);
        StdOut.println(cnt);
        if (cnt < 10) {
            printAll(a);
        }
    }
}

20.Bitonic search(双调查线).An array is bitonic if it is comprised of an increasing sequence of integers followed immediately by a decreasing sequence of integers. Write a program that, given a bitonic array of N distinct int values, determines whether a given integer is in the array. Your program should use ~ 3 lg N compares in the worst case.

Answer: Use a version of binary search, as in BitonicMax.java, to find the maximum (in ~ 1 lg N compares); then use binary search to search in each piece (in ~ 1 lg N compares per piece).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class BitonicMax{
    public static int[] bitonic(int N){
        int mid = StdRandom.uniform(N);
        int[] a = new int[N];
        for(int i=1; i<mid; i++){
            a[i] = a[i-1] + 1 + StdRandom.uniform(9);
        }
        if(mid > 0) a[mid] = a[mid-1] + StdRandom.uniform(10) - 5;
        for(int i = mid+1; i<N; i++){
            a[i] = a[i-1] - 1 - StdRandom.uniform(9);
        }
        for(int i = 0;i < N; i++){
            StdOut.println(a[i]);
        }
        return a;
    }
    public static int max(int[] a,int lo,int hi){
        if(hi == lo) return hi;
        int mid = lo + (hi-lo)/2;
        if(a[mid] <a[mid+1]) return max(a,mid+1,hi);
        if(a[mid] >a[mid+1]) return max(a,lo,mid);
        else return mid;
    }
    public static void main(String[] args){
        int N = Integer.parseInt(args[0]);
        int[] a = bitonic(N);
        StdOut.println("max = " + a[max(a,0,N-1)]);
    }
}

web exercise

13 Search in a sorted, rotated list. Given a sorted list of N distinct integers that has been rotated an unknown number of positions,e.g., 15 36 1 7 12 13 14, write a program RotatedSortedArray.java to determine if a given integer is in the list. The order of growth of the running time of your algorithm should be log N.

31 Given an array a[] of N real numbers, design a linear-time algorithm to find the maximum value of a[j] - a[i] where j ≥ i.

1
2
3
4
5
6
double best = 0.0;
double min = a[0];
for(int i=0; i < N; i++){
  min = Math.min(a[i], min);
  best = Math.max(a[i] - min, best);
}