caxapa.ru :: набыдлокодил КвикСорт (быстрая рекурсивная сортировка), смотрю тест на 500 значений, показывает 53000 рекурсивных вызовов, соответственно 21500 вложений, а МК не завис... ОЗУ всего 32к. Что я делаю не так?

IBAH (16.05.2016 16:32, просмотров: 5158)

набыдлокодил КвикСорт (быстрая рекурсивная сортировка), смотрю тест на 500 значений, показывает 53000 рекурсивных вызовов, соответственно 21500 вложений, а МК не завис... ОЗУ всего 32к. Что я делаю не так?

Ответить

- Алгоритм быстрой сортировки требует вложенность стека, в худшем случае, сопоставимую с размером сортируемого массива (C) - fk0(17.05.2016 10:51, ссылка)
- Метод деления пополам? Я, может быть, чего-то не понимаю, но 2⁹=512. То есть глубина вложенности 9. Ой. Спутал с поиском. - SciFi(16.05.2016 16:37 - 16:39)
  - Все допетрил! если считать дерево вызовов симметричным, получается высота =log2(53000)~16!!! а я уже грешным делом подумал, что у арма какая-то спецзагогулина для рекурсии... - IBAH(16.05.2016 16:47)
    - 16 факториал - это очень много! - Крок(16.05.2016 17:04)
      - не 16 факториал, а трижды факториал ("16!!!") - IBAH(17.05.2016 08:12)
        
        Я даже вообразить такое число не могу! - Крок(17.05.2016 08:41)
        
        Порвись! - Николай Коровин(17.05.2016 17:46, ссылка, картинка)
        
        Ох уж эти математики... Я полагаю, про такого рода творчество говорят "бумага всё стерпит"? :-) - SciFi(18.05.2016 15:17)
        
        Что только не придумают, лишь бы только яму не копать. - blackprapor(18.05.2016 16:17)
        
        Обычно такое говорит академик Скорпион :-) - SciFi(18.05.2016 16:23)
        
        Бздынь!!!! - Крок(17.05.2016 18:07)
        
        Ы. А у меня было скорее типа «трррррррррррр», когда я ЭТО читал О_о - Николай Коровин(17.05.2016 18:55)

ARM, RISC-V контроллеры