S**Y
发帖数: 136 | 1 1. 就是什么时候用O(n^2)的算法而不是用O(nlgn)的算法,比如用在数目少的时候会用i
nsertion sort,而不是用merge sort之类的?
2. 写个memmove function,这个谁能给个bug free的code,除了要考虑前后可能的overl
ap之外,还要考虑其他的么?谢谢 |
k***e
发帖数: 556 | 2 1. your example already gives one case: space constraint
the other case, for the problem size is not infinte, sometimes the const
before the bounds should be considered
用i
overl
【在 S**Y 的大作中提到】
: 1. 就是什么时候用O(n^2)的算法而不是用O(nlgn)的算法,比如用在数目少的时候会用i
: nsertion sort,而不是用merge sort之类的?
: 2. 写个memmove function,这个谁能给个bug free的code,除了要考虑前后可能的overl
: ap之外,还要考虑其他的么?谢谢
|
c****s
发帖数: 241 | 3 我来试试第一个问题：
选择那个算法，时间复杂度不是唯一的条件。还有考虑到空间复杂性，编程的复杂性，
和程序的可扩展性。比如，算法可以在1000台机器上运行，这个就很重要
用i
overl
【在 S**Y 的大作中提到】
: 1. 就是什么时候用O(n^2)的算法而不是用O(nlgn)的算法,比如用在数目少的时候会用i
: nsertion sort,而不是用merge sort之类的?
: 2. 写个memmove function,这个谁能给个bug free的code,除了要考虑前后可能的overl
: ap之外,还要考虑其他的么?谢谢
|
S**Y
发帖数: 136 | 4 space constraint是的,
但是有一个算法是: 对于sort数目比较多的数,先用merge sort或者quick sort, 在
sort数目
比较小的时候部分的时候改用insertion sort, 请问这么做是为什么?应该不是space的
考虑..
谢谢
const
【在 k***e 的大作中提到】
: 1. your example already gives one case: space constraint
: the other case, for the problem size is not infinte, sometimes the const
: before the bounds should be considered
:
: 用i
: overl
|
k***e
发帖数: 556 | 5 i already answered that: the const before n^2 and nlogn is very important
space的
【在 S**Y 的大作中提到】
: space constraint是的,
: 但是有一个算法是: 对于sort数目比较多的数,先用merge sort或者quick sort, 在
: sort数目
: 比较小的时候部分的时候改用insertion sort, 请问这么做是为什么?应该不是space的
: 考虑..
: 谢谢
:
: const
|
S**Y
发帖数: 136 | 6 我算了下,没觉得insertion sort n^2前的const比quick sort的nlgn前的const小啊
【在 k***e 的大作中提到】
: i already answered that: the const before n^2 and nlogn is very important
:
: space的
|
r**u
发帖数: 1567 | 7 and the cost of recursion, also insertion needs O(1) extra space, merge sort
needs O(n).
space的
【在 S**Y 的大作中提到】
: space constraint是的,
: 但是有一个算法是: 对于sort数目比较多的数,先用merge sort或者quick sort, 在
: sort数目
: 比较小的时候部分的时候改用insertion sort, 请问这么做是为什么?应该不是space的
: 考虑..
: 谢谢
:
: const
|
S**Y
发帖数: 136 | 8 并没有解释为什么在数目小的时候改用insertion sort啊
sort
【在 r**u 的大作中提到】
: and the cost of recursion, also insertion needs O(1) extra space, merge sort
: needs O(n).
:
: space的
|
w*********l
发帖数: 1337 | 9 1. merge sort空间开销大。而且insertion sort对于基本有序的数组排列是很快的，
比如quicksort最后一步就是用insertion sort
2. 应该就是两种overlap。想看实现去爬visual studio或者glibc的代码。
用i
overl
【在 S**Y 的大作中提到】
: 1. 就是什么时候用O(n^2)的算法而不是用O(nlgn)的算法,比如用在数目少的时候会用i
: nsertion sort,而不是用merge sort之类的?
: 2. 写个memmove function,这个谁能给个bug free的code,除了要考虑前后可能的overl
: ap之外,还要考虑其他的么?谢谢
|
w*********l
发帖数: 1337 | 10 恩。正好我的帖子回答这个问题了。这是当年经典的数据结构结论啊，你们老师没讲过？
【在 S**Y 的大作中提到】
: 并没有解释为什么在数目小的时候改用insertion sort啊
:
: sort
|
|
|
S**Y
发帖数: 136 | 11 谢谢
你意思是在数目小的时候,就基本有序了?
【在 w*********l 的大作中提到】
: 1. merge sort空间开销大。而且insertion sort对于基本有序的数组排列是很快的，
: 比如quicksort最后一步就是用insertion sort
: 2. 应该就是两种overlap。想看实现去爬visual studio或者glibc的代码。
:
: 用i
: overl
|
l*******r
发帖数: 511 | 12 你算算看，n^2和nlogn是有交点的，交点前当然要用n^2了，然后还有不同的系数
【在 S**Y 的大作中提到】
: 并没有解释为什么在数目小的时候改用insertion sort啊
:
: sort
|
j**w
发帖数: 382 | 13 O(nlogn) might have a HUGE constant, say, 10^6 * n * log n + 10^10, or very
hard to implement correctly for all possible input data. |
j**0
发帖数: 11 | 14 For problem 2, also think about the wrap around scenario (for example,
destination address range going over 4G on a 32 bit machine).
When I was asked this question, the interviewer also wanted me to come up
with as many optimization tricks as possible. I said, use pointer instead of
array indexing. He wanted more, and hinted upon memory alignment. So I said
, on a 32 bit machine, use an int pointer to copy 4 bytes at a time. But
these 4 byte chucks need to be memory aligned for faster speed. So |
w*********l
发帖数: 1337 | 15 这两个有交点不代表an^2+bn+c跟nlogn有交点啊
【在 l*******r 的大作中提到】
: 你算算看，n^2和nlogn是有交点的，交点前当然要用n^2了，然后还有不同的系数
|
K*****n
发帖数: 65 | 16 For Problem 2, copied from Visual Studio
;memmove - Copy source buffer to destination buffer
;
;Purpose:
; memmove() copies a source memory buffer to a destination memory
buffer.
; This routine recognize overlapping buffers to avoid propogation.
; For cases where propogation is not a problem, memcpy() can be used.
;
; Algorithm:
;
; void * memmove(void * dst, void * src, size_t count)
; {
; void * ret = dst;
;
; if (dst <= src || dst >= |
r****o
发帖数: 1950 | 17 为什么左边是dst<=src，右边是dst>=(src+count)
我觉得左边应该是dst<=(src-count)，
对不对?
【在 K*****n 的大作中提到】
: For Problem 2, copied from Visual Studio
: ;memmove - Copy source buffer to destination buffer
: ;
: ;Purpose:
: ; memmove() copies a source memory buffer to a destination memory
: buffer.
: ; This routine recognize overlapping buffers to avoid propogation.
: ; For cases where propogation is not a problem, memcpy() can be used.
: ;
: ; Algorithm:
|
