Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
Динамічна задача (англ. dynamic problem) в теорії обчислювальної складності належить до задач, які висвітлюються в термінах зміни вхідних даних. У найбільш загальному вигляді проблема в цій категорії зазвичай викладається наступним чином:
- Враховуючи клас вхідних об'єктів, знайдіть ефективні алгоритми та структури даних, щоб відповідати на певний запит щодо набору вхідних об'єктів кожного разу, коли змінюються вхідні дані, тобто об'єкти вставляються або видаляються.
Проблеми цього класу мають наступні заходи складності:
- Простір — обсяг пам'яті, необхідний для зберігання структури даних;
- Час ініціалізації — час, необхідний для початкової побудови структури даних;
- Час вставки — час, необхідний для оновлення структури даних, коли додається ще один елемент вводу;
- Час видалення — час, необхідний для оновлення структури даних, коли елемент вводу видаляється;
- Час запиту — час, необхідний для відповіді на запит;
- Інші операції, що стосуються розглянутої проблеми;
Загальний набір розрахунків для динамічної задачі називається динамічним алгоритмом.
Багато алгоритмічних задач, що висуваються в термінах фіксованих вхідних даних (так звані статичні проблеми в цьому контексті і вирішуються статичними алгоритмами), мають значущі динамічні версії.
Спеціальні випадки
Інкрементні алгоритми або онлайн алгоритми — це алгоритми, в яких допускаються лише додавання елементів, можливо, починаючи з порожніх/тривіальних вхідних даних.
Декрементальні алгоритми є алгоритмами, в яких допускаються лише видалення елементів, починаючи з ініціалізації повної структури даних.
Якщо допускаються і видалення і додавання, алгоритм іноді називають повністю динамічним.
Приклади
Максимальний елемент
- Статична задача
- Для множини з N чисел знайдіть максимальний елемент.
Задача може бути вирішена за час O(N).
- Динамічна задача
- Для початкової множини з N чисел динамічно підтримувати максимальне значення, коли допускаються операції вставки та видалення елементів.
Відоме рішення для цієї задачі є використання самозбалансованого бінарного дерева пошуку. Дерево займає O(N) пам'яті, спочатку може бути побудовано за час O (N log N) і забезпечує операції вставки, видалення та запиту з часом виконання O (log N).
- Задача підтримки черги з пріоритетом
- У спрощеному варіанті цієї динамічної задачі, потрібно видалити за один запит лише максимальний елемент. В такому варіанті можна опрацьовувати простіші структури даних.
Графи
Використовуючи граф, зверніть увагу на такі параметри, як зв'язність, максимальний ступінь, найкоротші шляхи і т. Д., Коли дозволяється вставляти та видаляти її краї.
Див. також
- [en]
- [en]
Література
- D. Eppstein, , and . «Dynamic graph algorithms». In CRC Handbook of Algorithms and Theory of Computation, Chapter 22. CRC Press, 1997.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Ne plutati z dinamichne programuvannya Dinamichna zadacha angl dynamic problem v teoriyi obchislyuvalnoyi skladnosti nalezhit do zadach yaki visvitlyuyutsya v terminah zmini vhidnih danih U najbilsh zagalnomu viglyadi problema v cij kategoriyi zazvichaj vikladayetsya nastupnim chinom Vrahovuyuchi klas vhidnih ob yektiv znajdit efektivni algoritmi ta strukturi danih shob vidpovidati na pevnij zapit shodo naboru vhidnih ob yektiv kozhnogo razu koli zminyuyutsya vhidni dani tobto ob yekti vstavlyayutsya abo vidalyayutsya Problemi cogo klasu mayut nastupni zahodi skladnosti Prostir obsyag pam yati neobhidnij dlya zberigannya strukturi danih Chas inicializaciyi chas neobhidnij dlya pochatkovoyi pobudovi strukturi danih Chas vstavki chas neobhidnij dlya onovlennya strukturi danih koli dodayetsya she odin element vvodu Chas vidalennya chas neobhidnij dlya onovlennya strukturi danih koli element vvodu vidalyayetsya Chas zapitu chas neobhidnij dlya vidpovidi na zapit Inshi operaciyi sho stosuyutsya rozglyanutoyi problemi Zagalnij nabir rozrahunkiv dlya dinamichnoyi zadachi nazivayetsya dinamichnim algoritmom Bagato algoritmichnih zadach sho visuvayutsya v terminah fiksovanih vhidnih danih tak zvani statichni problemi v comu konteksti i virishuyutsya statichnimi algoritmami mayut znachushi dinamichni versiyi Specialni vipadkiInkrementni algoritmi abo onlajn algoritmi ce algoritmi v yakih dopuskayutsya lishe dodavannya elementiv mozhlivo pochinayuchi z porozhnih trivialnih vhidnih danih Dekrementalni algoritmi ye algoritmami v yakih dopuskayutsya lishe vidalennya elementiv pochinayuchi z inicializaciyi povnoyi strukturi danih Yaksho dopuskayutsya i vidalennya i dodavannya algoritm inodi nazivayut povnistyu dinamichnim PrikladiMaksimalnij element Statichna zadacha Dlya mnozhini z N chisel znajdit maksimalnij element Zadacha mozhe buti virishena za chas O N Dinamichna zadacha Dlya pochatkovoyi mnozhini z N chisel dinamichno pidtrimuvati maksimalne znachennya koli dopuskayutsya operaciyi vstavki ta vidalennya elementiv Vidome rishennya dlya ciyeyi zadachi ye vikoristannya samozbalansovanogo binarnogo dereva poshuku Derevo zajmaye O N pam yati spochatku mozhe buti pobudovano za chas O N log N i zabezpechuye operaciyi vstavki vidalennya ta zapitu z chasom vikonannya O log N Zadacha pidtrimki chergi z prioritetom U sproshenomu varianti ciyeyi dinamichnoyi zadachi potribno vidaliti za odin zapit lishe maksimalnij element V takomu varianti mozhna opracovuvati prostishi strukturi danih Grafi Vikoristovuyuchi graf zvernit uvagu na taki parametri yak zv yaznist maksimalnij stupin najkorotshi shlyahi i t D Koli dozvolyayetsya vstavlyati ta vidalyati yiyi krayi Div takozh en en LiteraturaD Eppstein and Dynamic graph algorithms In CRC Handbook of Algorithms and Theory of Computation Chapter 22 CRC Press 1997