Ожидаемое время работы: для часто ожидаемого времени работы просто означает среднее время работы для случайных входов.Но если речь идет о рандомизированном алгоритме, который имеет место в данном случае, это означает, что алгоритм запускает входные данные со случайным выбором, сделанным алгоритмом.
Проверка времени выполнения: Что касается проверки работы тета n (logn)время быстрой сортировки, это будет связано с более сложной математикой, вот ссылка из CMU, которая доказывает время работы тета n (logn) (https://www.cs.cmu.edu/~avrim/451f11/lectures/lect0906.pdf).
Не заморачиваться со сложной математикой, я только собираюсьсосредоточиться на том, как мы можем понять это время выполнения с помощью интуиции
Неслучайные входы: если каждый стержень имеет ранг где-то в середине 50 процентов, то есть между 25-м процентилем и 75-м процентилем, то он разделяетэлементы с не менее 25% и не более 75% с каждой стороны. Затем разделение данных дает нам O (logn), а вызов по каждому из них дает нам общее время выполнения тета nlog (n). Убедитесь, что вы понимаете, почему этонерандомизированная быстрая сортировка имеет среднее время выполнения тета nlog (n).
Теперь давайте поговорим оожидаемое время работы рандомизированной быстрой сортировки ...
Если входные данные случайные, то разворот не гарантирован, чтобы быть в середине 50 процентов.Тем не менее, когда мы начинаем со случайного центра, он будет в середине примерно 50 процентов в течение примерно половины времени.Представьте, что вы подбрасываете монету, пока не получите n голов.В среднем, вам нужно будет перевернуть только 2 раза.Точно так же рекурсия Quicksort завершится в ожидаемые 2 раза из того, что потребуется для неслучайных входных данных, которые должны быть только постоянными, кратными O (logn).Каждый уровень дерева вызовов будет вызываться по n раз, ожидаемая общая работа все равно будет равна тета (nlogn).