cs61b week7 -- Asymptotics ||

Example 1 For循环

public static void printParty(int N) {
for (int i = 1; i <= N; i = i * 2) {
for (int j = 0; j < i; j += 1) {
System.out.println("hello");
int ZUG = 1 + 1;
}
}
}

System.out.println("hello);

N = 2,已知i = 1的结果，只需再求i = 2的结果再将前面算得的i = 1的结果相加,即 3 = 1 + 2

......

$$C(N) = 1 + 2 + 4 + 8 + ...... + N$$

$$S_{n} = \frac{a_{1}(1 - q^{n})}{1 - q}$$

$$C(N) = \frac{1 - 2^{1 + log_{2}N}}{1 - 2} = 2N - 1$$

• 找出精确的和
• 写例子
• 画图

Example 2 递归树

public static int f(int n) {
if (n <= 1)
return 1;
return f(n-1) + f(n-1);
}

Solution 1

C(1) = 1
C(2) = 1 + 2
C(3) = 1 + 2 + 4
.......
C(N) = 1 + 2 + 4 + ... + $$2^{N - 1}$$

$$C(Q) = 1 + 2 + 4 + ... + Q = 2Q - 1$$

$$C(Q) = 2Q - 1 = 2 \cdot 2^{N - 1} - 1 = 2^{N} - 1$$

Solution 2

C(1) = 1
C(N) = 2C(N - 1) + 1
= 2(2C(N - 2) + 1) + 1
= 2(2(2C(N - 3) + 1) + 1) + 1
......
= 2(...2C(N - (N - 1)) + 1 ).... + 1
= 2^(N - 1)C(1) + 1 + 2 + 4 + ... + 2^((N - 1) - 1)
= 2^(N - 1) + 2^(N - 2) + 2^(N - 3) + ... + 4 + 2 + 1
= 2^N - 1

Example 3 BinarySearch

直观分析

$$1 = \frac{N}{2^{C}}$$

$$C = log_{2}{N}$$

精确分析

$$C(N) = ⌊log_{2}(N)⌋+1$$

$$C(N) = \Theta(log_{2}N)$$吗？

$$⌊f(N)⌋=\Theta(f(N))$$

proof：

$$f(N) - \frac{1}{2} \le ⌊f(N) - \frac{1}{2}⌋ \le f(N) + \frac{1}{2}$$

$$⌊f(N)⌋=\Theta(f(N))$$

$$⌈f(N)⌉=\Theta(f(N))$$

$$log_{P}(N) = \Theta(log_{Q}(N))$$

二分查找代码的瑕疵

static int binarySearch(String[] sorts, String x, int lo, int hi)
if (lo > hi) return -1;
int m = (lo + hi) / 2;
int cmp = x.compareTo(sorted[m]);
if (cmp < 0) return binarySearch(sorted, x, lo, m - 1);
else if (cmp > 0) return binarySearch(sorted, x, m + 1, hi);
else return m;
}


$$m = \frac{(lo + hi)}{2}$$

$$当 lo + hi > 2^{31} - 1$$时，即超过了int 的最大值时，会发生溢出，导致m变成负数，从而引发数组ArrayIndexOutOfBoundsException

int mid = low + ((high - low) / 2);

int mid = (low + high) >>> 1;

mid = ((unsigned int)low + (unsigned int)high)) >> 1;

Example 4 MergeSort

MergeSortDemo

直观分析

$$K = log_{2}N$$

......

$$f(N) = K\cdot N=Nlog_{2}N$$