Алгоритмы и структуры данных осень 2013 лекция 4

  • Published on
    09-Jul-2015

  • View
    473

  • Download
    4

Embed Size (px)

Transcript

  • : 2

  • 21.

    2.

    3.

  • 2^k m.

    1 2, 3 4, n-1 n .

    3,

    3

  • 4

  • 2

    ,

    -

    ,

    -

    5

  • 2

    void merge(int *a, int a_len, int *b,

    b_len, int *c) {

    int i=0; int j=0;

    for (;i < a_len and j < b_len;) {

    if (a[i] < b[j]) {

    c[i+j] = a[i];

    ++i;

    } else {

    c[i+j] = b[j];

    ++j;

    }

    }

    if (i==a_len) {

    for (;j < b_len;++j) { c[i+j] = b[j];

    }

    } else {

    for (;i < a_len;++i) { c[i+j] = a[i];

    }

    }

    }

    6

  • 2

    O(n+m)

    : min(n,m)

    n+m

    7

  • K-

    k n : A1, A2, .. Ak

    A1..Ak

    , 1

    log(k)

    O(n*log(k))

    8

  • K-

    : n

    log(k) 2

    9

  • K-

    k O(k)

    O(1)

    O(1)

    O(log(k))

    O(k + n*log(k))

    10

  • 11

  • 12

  • + O(n) - linear time

    + stable

    +

    - O(n)

    - O(n)

  • LSD raddix sort

  • LSD raddix sort

  • LSD raddix sort

  • LSD raddix sort

    + O(n*key len)

    + O(n)

    + stable

    - cant use unstable sort for buckets

  • MSD raddix sort

  • MSD raddix sort

  • MSD raddix sort

    + O(n*key_len) *

    + O(n)

    + 1

    + could be unstable

    -

  • MSD vs LSD

  • ?

    *

    - LSD ~

    + MSD

  • ?

    LSD

  • MSD sort vs QuickSort

    == 1

  • Binary QuickSort

    o 0

    o 1

  • Binary quicksort

  • 3-way split

  • 3-way raddix quick sort

  • 3-way raddix quick sort

  • !

    @mail.ru

Recommended

View more >