час
: O(N*LogN), де N – кількість заданих елементів.
Основним кроком, який займає час, є сортування всіх предметів у порядку зменшення їх співвідношення вартості/ваги. Якщо елементи вже впорядковані в необхідному порядку, цикл while займає O(n) часу. Середня складність швидкого сортування за часом становить O (nlogn). Таким чином, загальний час, витрачений на сортування, становить O(nlogn).
Часова складність У вас є 2 цикли, які займають O(N) часу кожен, і одна функція сортування, яка займає O(N * logN). Тому загальна часова складність становить O(2 * N + N * logN) = O(N * logN).
По-перше, ми дали рюкзак максимальної місткості m кг і n предметів із зазначенням їх ваги та прибутку. Заповніть рюкзак підмножиною предметів так, щоб вибрана вага була меншою або дорівнювала місткості рюкзака, а прибуток предметів був максимальним.
Часова складність GREEDY-ACTIVITY-SELECTOR становить O(n2) (за умови, що операції оновлення набору коштують лише один крок кожна!).
Пояснення: Проблему ранця 0-1 не можна вирішити жадібним методом тому що він включений, щоб заповнити рюкзак на повну, тому тут жадібний алгоритм не є оптимальним. Задача рюкзака 0-1 розв’язана за допомогою підходу динамічного програмування.
Задачу ранця 0/1 неможливо розв’язати жадібним алгоритмом, оскільки він не виконує властивості жадібного вибору та властивості оптимальної підструктури, як згадувалося раніше. Правила: кожен предмет має вагу та вартість.