| dbo:abstract
|
- Dynamic problems in computational complexity theory are problems stated in terms of the changing input data. In the most general form a problem in this category is usually stated as follows:
* Given a class of input objects, find efficient algorithms and data structures to answer a certain query about a set of input objects each time the input data is modified, i.e., objects are inserted or deleted. Problems of this class have the following measures of complexity:
* Space – the amount of memory space required to store the data structure;
* Initialization time – time required for the initial construction of the data structure;
* Insertion time – time required for the update of the data structure when one more input element is added;
* Deletion time – time required for the update of the data structure when an input element is deleted;
* Query time – time required to answer a query;
* Other operations specific to the problem in question The overall set of computations for a dynamic problem is called a dynamic algorithm. Many algorithmic problems stated in terms of fixed input data (called static problems in this context and solved by static algorithms) have meaningful dynamic versions. (en)
- Динамічна задача (англ. dynamic problem) в теорії обчислювальної складності відноситься до задач, які висвітлюються в термінах зміни вхідних даних. У найбільш загальному вигляді проблема в цій категорії зазвичай викладається наступним чином:
* Враховуючи клас вхідних об'єктів, знайдіть ефективні алгоритми та структури даних, щоб відповідати на певний запит щодо набору вхідних об'єктів кожного разу, коли змінюються вхідні дані, тобто об'єкти вставляються або видаляються. Проблеми цього класу мають наступні заходи складності:
* Простір — обсяг пам'яті, необхідний для зберігання структури даних;
* Час ініціалізації — час, необхідний для початкового побудови структури даних;
* Час вставки — час, необхідний для оновлення структури даних, коли додається ще один елемент вводу;
* Час видалення — час, необхідний для оновлення структури даних, коли елемент вводу видаляється;
* Час запиту — час, необхідний для відповіді на запит;
* Інші операції, що стосуються розглянутої проблеми; Загальний набір розрахунків для динамічної задачі називається динамічним алгоритмом. Багато алгоритмічних задач, що висуваються в термінах фіксованих вхідних даних (так звані статичні проблеми в даному контексті і вирішуються статичними алгоритмами), мають значущі динамічні версії. (uk)
|
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 3055 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- Dynamic problems in computational complexity theory are problems stated in terms of the changing input data. In the most general form a problem in this category is usually stated as follows:
* Given a class of input objects, find efficient algorithms and data structures to answer a certain query about a set of input objects each time the input data is modified, i.e., objects are inserted or deleted. Problems of this class have the following measures of complexity: The overall set of computations for a dynamic problem is called a dynamic algorithm. (en)
- Динамічна задача (англ. dynamic problem) в теорії обчислювальної складності відноситься до задач, які висвітлюються в термінах зміни вхідних даних. У найбільш загальному вигляді проблема в цій категорії зазвичай викладається наступним чином:
* Враховуючи клас вхідних об'єктів, знайдіть ефективні алгоритми та структури даних, щоб відповідати на певний запит щодо набору вхідних об'єктів кожного разу, коли змінюються вхідні дані, тобто об'єкти вставляються або видаляються. Проблеми цього класу мають наступні заходи складності: (uk)
|
| rdfs:label
|
- Dynamic problem (algorithms) (en)
- Динамічна задача (uk)
|
| owl:differentFrom
| |
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:knownFor
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
