Введение в анализ сложности алгоритмов (часть 4)

[backmeupplz]

Спасибо за статью! Правда, все это в универе прошли — но задачки-минутки размять мозг всегда хороши :)

[AveNat]

На здоровье!

[ylibatsya]

Спасибо тебе, автор. Хороший текст и хороший перевод. Прочитала все 4 статьи в качестве подготовки в собеседованию, и заодно поставила галочку напротив «узнать наконец-то про сложность алгоритмов».

[Demven]

Каждый раз при собеседовании меня спрашивают про сложность алгоритмов и каждый раз приходилось краснеть и мысленно ставить галочку «срочно разобраться в этой теме!». Ваши статьи очень помогли, огромное спасибо!

[arturdumchev]

Спасибо за перевод статей!

Кажется, нашел опечатку у вас.
В этой функции вы считаете массив от 0-го элемента (то есть первый элемент имеет индекс 0)

def merge( A, B ):
    if empty( A ):
        return B
    if empty( B ):
        return A
    if A[ 0 ] < B[ 0 ]:
        return concat( A[ 0 ], merge( A[ 1...A_n ], B ) )
    else:
        return concat( B[ 0 ], merge( A, B[ 1...B_n ] ) )

Но в следующей функции первый элемент у вас под индексом 1, а не 0. leftHalf ведь нужно брать с 0-го элемента.

def mergeSort( A, n ):
    if n = 1:
        return A # it is already sorted
    middle = floor( n / 2 )
    leftHalf = A[ 1...middle ]
    rightHalf = A[ ( middle + 1 )...n ]
    return merge( mergeSort( leftHalf, middle ), mergeSort( rightHalf, n - middle ) )

[Sergery8205]

Очень полезная серия статей. Спасибо за перевод! Помогает упорядочить, а то малость каша осталась в голове про тета, О и омега.