Почему в таком случае сложность алгоритма оценивается в O(n**2)?. Нужно

Question

Python beginners

gerald

Почему в таком случае сложность алгоритма оценивается в O(n**2)?. Нужно

отсортировать список от найбольшего кол-ва произведений к найменьшему?

#backend #programming #python #russian

0

14.05.2023

11 ответов

14 просмотров

Const

А где тут что-либо сказано про используемый алгоритм сортировки?

0

14.05.2023

gerald Автор вопроса

Arkady Strugatsky
А что за алгоритм хоть? По скриншоту не понятно

Вы хотите отсортировать список по убыванию счетчика воспроизведений, чтобы самые любимые исполнители стояли на первых местах. Как это сделать? Одно из возможных решений - пройти по списку и найти исполнителя с наибольшим количеством воспроизведений. Этот исполнитель добавляu ется в новыи список.

0

14.05.2023

Arkady Strugatsky

gerald
Вы хотите отсортировать список по убыванию счетчик...

Ну да, это O(n^2)

0

14.05.2023

Const

gerald
Вы хотите отсортировать список по убыванию счетчик...

Это "наивная" сортировка, я честно говоря даже название алгоритма не помню Для каждого элемента (n) проходимся по всему исходному списку (n) ==> n*n

0

14.05.2023

Arkady Strugatsky

gerald
Вы хотите отсортировать список по убыванию счетчик...

Следи за руками. Вставка в результирующий список - это O(1) Таких вставок нам нужно n. Получаем O(n) На каждую вставку нам нужно найти максимальное значение. Поиск максимума это O(n). Умножаем, получаем O(n^2)

0

14.05.2023

gerald Автор вопроса

Const
Это "наивная" сортировка, я честно говоря даже наз...

Название алгоритма: сортировка выбором

0

14.05.2023

gerald Автор вопроса

Arkady Strugatsky
Следи за руками. Вставка в результирующий список -...

Спасибо

0

14.05.2023