R语言代写 | R代写 | 算法代写:这是一个典型的R类型的题目代写
1.
a.
8, 77
1, 2, 32, 63
b.
the worst case is that all arrays have been considered。 so the
search time is the sum of （1, 2, 4, 8…n/2）size binary search.
so the worst time O(log(n) + log(n/2) + log(n/4) + . . . + 1) =
O(log2(n))
c. the worst insertion is that when insert new array at the linked
list, then we need merge until only one array left in the linked
list.so the worst time is O(log n)
d. as table shows, double seperate blank (‘||’) means that after insertion,
the set contains only one array.
| insert | 1 || 2 || 3 | 4 || 5 | 6 | 7 | 8 || …
| — | — || — || — | — || — | — | — | — || …
| cost | 1 || 2 || 1 | 4 || 1 | 2 | 1 | 8 || …
suppose that 2^{k-1} < n <= 2^k, now JUST consider the insertion between that, the insertion with odd times cost 1, and that with even times cost will be summing up as 2^{k+1} - 2*k. [remark: the detail is here, 2^k + \sum_{i=2}^{k-1} (i-1)*2^{k-i} = 2^k + (2^k - 2*k) = 2^{k+1} - 2*k ] so by aggregae method: T(n) <= \sum_{k=1}^{log n} (2^{k+1} - 2*k) + n/2 < 2n * log n + n/2 so the amortized insertion time is T(n) / n = O(log n) e. using the accounting method, when insert an element, we account its current cost as 1, and its future cost is determined by the one which will influence its position. As the table shows | insert | 1 || 2 || 3 | 4 || 5 | 6 | 7 | 8 || | that will influence it | 2,4,8 || 4,8 || 4,8 | 8 || 6,8 | 8 | 8 | - || | cost | 1+3=4 || 1+2=3 || 1+2=3 | 1+1=2 || 3 | 2 | 2 | 1 || T(n) <= 2^{k-1} + 1 + k \sum_{i=1}^{k-2} 2^i < n + 1 + log n * n so the amortized insertion time is T(n) / n = O(log n) 2. a. make_set(1) make_set(2) make_set(3) make_set(4) make_set(5) make_set(6) make_set(7) make_set(8) union(2, 1) union(4, 3) union(3, 1) union(6, 5) union(8, 7) union(7, 5) union(5, 1) 1 ---- 2 ---- 3 ---- 4 ---- 5 ---- 6 ---- 7 ---- 8 b. 2^k c. infinite, if we need rank++, then x.rank == y.rank, but it's possible to build a very flat tree (for example, union(2, 1) union(3, 1) union(4, 1) union(5, 1))