Comments 6
Спасибо за статью! Правда, все это в универе прошли — но задачки-минутки размять мозг всегда хороши :)
Спасибо тебе, автор. Хороший текст и хороший перевод. Прочитала все 4 статьи в качестве подготовки в собеседованию, и заодно поставила галочку напротив «узнать наконец-то про сложность алгоритмов».
Каждый раз при собеседовании меня спрашивают про сложность алгоритмов и каждый раз приходилось краснеть и мысленно ставить галочку «срочно разобраться в этой теме!». Ваши статьи очень помогли, огромное спасибо!
Спасибо за перевод статей!
Кажется, нашел опечатку у вас.
В этой функции вы считаете массив от 0-го элемента (то есть первый элемент имеет индекс 0)
Но в следующей функции первый элемент у вас под индексом 1, а не 0. leftHalf ведь нужно брать с 0-го элемента.
Кажется, нашел опечатку у вас.
В этой функции вы считаете массив от 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 ) )
Очень полезная серия статей. Спасибо за перевод! Помогает упорядочить, а то малость каша осталась в голове про тета, О и омега.
Sign up to leave a comment.
Введение в анализ сложности алгоритмов (часть 4)