Анализ PSRS (параллельная сортировка по регулярной выборке) В вычислительной части. Почему Big-o Сортировка регулярных образцов: O (p ^ 2 log p ^ 2) = O (p ^ 2 log p)? Спасибо за ответ.
Поскольку log p² = 2 log p (это свойство логарифмов) и использование нотации Big-O позволяет игнорировать мультипликативную константу.
O (p ^ 2 log p ^ 2) = O (2p ^ 2 log p), по свойствам логарифмов. И O (кг) = O (г), где k является константой. Поэтому вы можете удалить 2, чтобы получить O (p ^ 2 log p).