Википедия утверждает, что среднее время выполнения алгоритма быстрого выбора ( Ссылка ) составляет O (n). Однако я не мог четко понять, как это Это так. Может ли кто-нибудь объяснить мне (через отношение рекурсии + использование основного метода), как среднее время выполнения составляет O (n)?