t**********s
发帖数: 930 | 1 How can I prove that it is Ω(n^2)
Too difficult for me.
Thanks! |
q*****g
发帖数: 72 | 2 worst case:
(n-1) + (n-2) + ... + 1 = n*(n-1)/2 = O(n^2);
average case is just half of worse case, which is also O(n^2)
【在 t**********s 的大作中提到】
: How can I prove that it is Ω(n^2)
: Too difficult for me.
: Thanks!
|
t**********s
发帖数: 930 | 3 I don't think that it is so simple.
It should be the running time on a array randomly permuted.
Say an array has n elements. Then there is n! possible arrays.
The average running time should be the average of the n! possible running
time.
【在 q*****g 的大作中提到】
: worst case:
: (n-1) + (n-2) + ... + 1 = n*(n-1)/2 = O(n^2);
: average case is just half of worse case, which is also O(n^2)
|
g**g
发帖数: 1575 | 4 find an algorithm book to read first... that saves you a lot of time
【在 t**********s 的大作中提到】
: I don't think that it is so simple.
: It should be the running time on a array randomly permuted.
: Say an array has n elements. Then there is n! possible arrays.
: The average running time should be the average of the n! possible running
: time.
|
