1:10:00 т.е. мы в функции sort (которая написана справа) можем использовать вместо rand свою функцию. Но кроме этого мы же можем намного проще сделать split (потому что мы знаем 3/10 элементов, которые будут левее и 3/10, которые будут правее)
@@pavelmavrin т.е. подразумевается интерес только в "макрооптимизациях"? А не могут ли подобные улучшения, влияющие только на константу сложности, дать ускорение на 10-15% (или выше) на часто используемых значениях длины сортируемого массива?
Есть ощущение, что в коде для функции split что-то осталось за пределами написанного в коде или сказанного вслух. Причем, в прошлых итерациях этого цикла лекций, объяснение ровно такое же (я проверил лекцию на эту тему в 2к19м году). В общем, код для функции split просто не обладает никаким capacity к тому, чтобы вынести элементы, большие чем X, направо от него. Возьмем array: 8 1 6 7 9 X: 6 получится всего одна перестановка 8 и 1, больше их не будет, потому что условие a[i] < x больше не будет выполняться после этой первой перестановки, в итоге получим 1 8 6 7 9 В общем, мне очень интересно, где я облажался
Код быстрой сортировки написан нерабочий. Пример - в начале вызова split: l=0, r=9, x=-20 a = [0, 2, 9, -20, 14, -16, -14, -12, -6, -1] В конце вызова split: m=0 a = [0, 2, 9, -20, 14, -16, -14, -12, -6, -1] Проблема в том, что все последующие вызовы не содержат нуля (ну кроме вызова sort(l=0, r=0) для этого нуля). По итогу в конце получится массив с нулём в самом начале: [0, -20, -16,...]
@@ИванЕвдокимов-л6ь Я говорю об этом в лекции. Если бесконечно будет выпадать m = 0, то действительно будет работать бесконечно. Но вероятность этого равна 0
19:00 подскажите, о какой функции идёт речь? Я так понимаю, что нужно минимизировать логарифм, но не могу формализовать Если исходить из того, что нужен минимум для log n/x по основанию x на [n/2, n], то тут и без производных понятно, что минимум будет при n/2, так как логарифм -- строго возрастающая функция
Тут идея такая. T(n)=n+T(n1)+T(n2), при этом n1+n2=n. Поэтому чтобы оценить сверху значение этой суммы, нужно найти максимум T(x)+T(n-x). Для меньших значений мы по индукции знаем, что T(n)=n log n, поэтому нам нужен максимум (x log x + (n-x) log (n-x)). Это функция выпуклая, поэтому у нее максимумы на краях отрезка.
@@pavelmavrin "Это функция выпуклая, поэтому у нее максимумы на краях отрезка." -- парабола тоже выпуклая но ее вершина может лежать в середине отрезка
1:10:00 т.е. мы в функции sort (которая написана справа) можем использовать вместо rand свою функцию. Но кроме этого мы же можем намного проще сделать split (потому что мы знаем 3/10 элементов, которые будут левее и 3/10, которые будут правее)
можем, непонятно зачем только. детерминированная сортировка за O(n log n) у нас и до этого была
@@pavelmavrin т.е. подразумевается интерес только в "макрооптимизациях"? А не могут ли подобные улучшения, влияющие только на константу сложности, дать ускорение на 10-15% (или выше) на часто используемых значениях длины сортируемого массива?
@@Олег-л4ф3е можно попробовать, но я думаю только медленнее станет
Есть ощущение, что в коде для функции split что-то осталось за пределами написанного в коде или сказанного вслух.
Причем, в прошлых итерациях этого цикла лекций, объяснение ровно такое же (я проверил лекцию на эту тему в 2к19м году).
В общем, код для функции split просто не обладает никаким capacity к тому, чтобы вынести элементы, большие чем X, направо от него.
Возьмем
array: 8 1 6 7 9
X: 6
получится всего одна перестановка 8 и 1, больше их не будет, потому что условие a[i] < x больше не будет выполняться после этой первой перестановки, в итоге получим
1 8 6 7 9
В общем, мне очень интересно, где я облажался
Ну вроде все так в примере, сначала элементы =6
@@pavelmavrin так ведь 1 8 6. 8 ведь не меньше 6 :(
@@andrewlazy662 (1) и (8 6 7 9)
@@pavelmavrin АААА, гениально...
Спасибо
Лайк, Респект. Спасибо.
47:20 `return a[l]`, видимо
Да, конечно
Код быстрой сортировки написан нерабочий.
Пример - в начале вызова split:
l=0, r=9, x=-20
a = [0, 2, 9, -20, 14, -16, -14, -12, -6, -1]
В конце вызова split:
m=0
a = [0, 2, 9, -20, 14, -16, -14, -12, -6, -1]
Проблема в том, что все последующие вызовы не содержат нуля (ну кроме вызова sort(l=0, r=0) для этого нуля). По итогу в конце получится массив с нулём в самом начале: [0, -20, -16,...]
У меня правая граница не включительно везде, поэтому левый запуск будет (0, 0), а правый (0, n)
@@pavelmavrin Я вроде бы так и написал. Проблема в том, что правая часть в этом примере (sort(0,n)) будет вызываться до бесконечности
@@ИванЕвдокимов-л6ь Я говорю об этом в лекции. Если бесконечно будет выпадать m = 0, то действительно будет работать бесконечно. Но вероятность этого равна 0
19:00 подскажите, о какой функции идёт речь? Я так понимаю, что нужно минимизировать логарифм, но не могу формализовать
Если исходить из того, что нужен минимум для log n/x по основанию x на [n/2, n], то тут и без производных понятно, что минимум будет при n/2, так как логарифм -- строго возрастающая функция
Тут идея такая. T(n)=n+T(n1)+T(n2), при этом n1+n2=n. Поэтому чтобы оценить сверху значение этой суммы, нужно найти максимум T(x)+T(n-x). Для меньших значений мы по индукции знаем, что T(n)=n log n, поэтому нам нужен максимум (x log x + (n-x) log (n-x)). Это функция выпуклая, поэтому у нее максимумы на краях отрезка.
@@pavelmavrin "Это функция выпуклая, поэтому у нее максимумы на краях отрезка." -- парабола тоже выпуклая но ее вершина может лежать в середине отрезка
@@РусланКазымов-т7у ну тут в другую сторону выпуклая же
Походу на свете есть три по-настоящему непонятные вещи: быстрая сортировка, быстрая речь и третья - не понятно, что из первых двух непонятнее.
Эти лосиные вопли Павла :))
первый комментарий! 😅