Бинарный поиск + Сортировка против Линейного поиска (Big O)

Question

У меня есть вопрос о проблеме, над которой я работаю.Я должен воспроизводить видео в случайном порядке, не повторяя видео.Каждое видео разрешено воспроизводить только один раз в каждом списке воспроизведения.Каждое видео имеет уникальный идентификатор от 0 до max_video_count, который определяется во время выполнения (в зависимости от сервера).

Что я делаю сейчас, я создал связанный список, который добавляет уникальный идентификатор каждого воспроизводимого видео.Затем я случайно создаю случайное число от 0 до max_video_count, делаю линейный поиск, если число уже есть в связанном списке, и если да, я вычисляю новое число .. и снова линейный поиск .. и так далее !!

очевидно, это не очень практично, и иногда требуется много времени, чтобы найти элемент.особенно, когда уже было воспроизведено много видео.

Я подумал, что вместо линейного поиска я реализую бинарный поиск, но это приводит меня к проблеме, заключающейся в том, что сначала мне нужно отсортировать список.Итак, следующим моим шагом было подумать, что я сортирую список, вставляя новый unique_id, а затем выполняю бинарный поиск.

Я знаю, что бинарный поиск - это O (log n) по сравнению с O (n) линейным поиском, что является большим прогрессом.Но сортировка списка также является O (n), потому что, чтобы найти правильное место, мне пришлось бы снова выполнить линейный поиск ..... Так что я пришел к решению, что этот двоичный поиск будет O (log N * n) по сравнению сO (n) линейный поиск -> линейный поиск быстро.Это правильно?Может быть, весь мой подход неверен ... но я еще не мог придумать что-то лучшее ...

Я совершенно новичок в алгоритмах, поэтому было бы неплохо, если бы кто-то мог просветить меня здесь :-)

Привет Маркус

Answer 1

По сути, вы просто смотрите на случайную перестановку .Расположите свои видео в одном фиксированном списке, а затем, чтобы создать список воспроизведения, произведите случайную перестановку этого списка и воспроизведите пермутированный список.

Типичный и эффективный (O (n)) способ достижения такогоперестановка осуществляется с помощью Кнута Шафла.

_{(На практике вы, конечно, можете просто создать случайную перестановку из набора индексов и воспроизводить элементы в порядке перестановочных индексов.)}

Answer 2

Если количество видео является фиксированным, вы можете просто использовать массив логических значений, инициализированных как false, для отслеживания того, что было воспроизведено - поиск с постоянным временем.Или используйте целые числа, считая количество воспроизведенных раз, если вместо этого вы хотите ограничить количество раз.

Если видео удаляются (или добавляются в) из списка в ходе воспроизведения, ассоциативный массив (внекоторые языки, называемые словарём или хешем), для отслеживания того, что было воспроизведено, возможно, проще.

Не реализуйте структуру самостоятельно (если только это не учебное упражнение, которое вы хотите), используйте то, что ваш языкВыбор может предложить.