B*****p
发帖数: 339 | 1 1st edition section 7.7 no. 6, 2nd edition, section 7.7, no. 12
After the array x[0,,N-1] is initialized to zero. N of the following
operations are performed
for i = L to U do
x[i] += V;
where L, U and V are parameters of each operation (L and U are integers
satisfying 0<=L<=U
real). After the N operations, the values of x[0] through x[N-1] are
reported in order. The method just
sketched requires O(N^2) time. Can you find a faster algorithm?
1. What is the value of L and U for e | Z*****Z
发帖数: 723 | 2
be
different
I think L and U are fixed for N operations.
The values of X[1] through X[N] is reported in order does not mean X is
sorted.
【在 B*****p 的大作中提到】
: 1st edition section 7.7 no. 6, 2nd edition, section 7.7, no. 12
: After the array x[0,,N-1] is initialized to zero. N of the following
: operations are performed
: for i = L to U do
: x[i] += V;
: where L, U and V are parameters of each operation (L and U are integers
: satisfying 0<=L<=U: real). After the N operations, the values of x[0] through x[N-1] are
: reported in order. The method just
: sketched requires O(N^2) time. Can you find a faster algorithm?
| K******g
发帖数: 1870 | 3 If L and U are fixed, then the question should be very easy. The complexity
will be O(N). Then what is the point of this problem?
【在 Z*****Z 的大作中提到】
:
: be
: different
: I think L and U are fixed for N operations.
: The values of X[1] through X[N] is reported in order does not mean X is
: sorted.
| b********h
发帖数: 119 | 4 After the N operations, the values of x[0] through x[N-1] are
The above words doesn't mean x[] is sorted. It just says after those N
operations, you are going to report the values in order. It doesn't matter
how are you going to do it. And it has nothing to do with the previously
described process.
The intent of this problem is asking you to give an algorithm that simulates
the described process in complexity less than O(N^2). | z*****o
发帖数: 40 | 5 我觉得 L, U 在不同时候是不同的，否则
否则 s = sum(V) 然后 for i = L to V do x[i] = v * N 就可以了
既然说 L, U, V are parameters of each operation, 我觉得他们就是每次可以不同
，否则为啥叫 parameters.
这个应该有 NlogN 的算法
把 L,U 看作一个线段，对所有的线段端点（2N个）排序，
s=0
从左到有扫描端点
如果遇到一个左端点，s+=线段对应的v
如果遇到一个右端点，s-=线段对应的v
处理完一个端点后，s就是x[这个端点+1]到x[下一个端点]的值
【在 B*****p 的大作中提到】
: 1st edition section 7.7 no. 6, 2nd edition, section 7.7, no. 12
: After the array x[0,,N-1] is initialized to zero. N of the following
: operations are performed
: for i = L to U do
: x[i] += V;
: where L, U and V are parameters of each operation (L and U are integers
: satisfying 0<=L<=U: real). After the N operations, the values of x[0] through x[N-1] are
: reported in order. The method just
: sketched requires O(N^2) time. Can you find a faster algorithm?
|
|
