Вычислительная сложность: различия между версиями
Patarakin (обсуждение | вклад) (Новая страница: «{{Понятие |Field_of_knowledge=Информатика |Environment=Scratch, Snap!, Python }} '''Вычисли́тельная сло́жность''' — понятие в информатике и теории алгоритмов, обозначающее функцию зависимости объёма работы, которая выполняется некоторым алго...») |
Patarakin (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
{{Понятие | {{Понятие | ||
|Description=Вычисли́тельная сло́жность — понятие в информатике и теории алгоритмов, обозначающее функцию зависимости объёма работы, которая выполняется некоторым алгоритмом, от размера входных данных. | |||
|Field_of_knowledge=Информатика | |Field_of_knowledge=Информатика | ||
|Environment=Scratch, Snap!, Python | |Environment=Scratch, Snap!, Python | ||
}} | }} | ||
'''Вычисли́тельная сло́жность''' — понятие в [[информатика|информатике]] и [[теория алгоритмов|теории алгоритмов]], обозначающее функцию зависимости объёма работы, которая выполняется некоторым алгоритмом, от размера входных данных. Раздел, изучающий вычислительную сложность, называется [[Теория сложности вычислений|теорией сложности вычислений]]. Объём работы обычно измеряется [[абстракция|абстрактными]] понятиями времени и пространства, называемыми [[Вычислительные ресурсы|вычислительными ресурсами]]. Время определяется количеством элементарных шагов, необходимых для решения задачи, тогда как пространство определяется объёмом памяти или места на [[носитель информации|носителе данных]]. Таким образом, в этой области предпринимается попытка ответить на центральный вопрос разработки алгоритмов: «как изменится время исполнения и объём занятой памяти в зависимости от размера входа?». Здесь под размером входа понимается длина описания данных задачи в [[бит]]ах (например, в [[задача коммивояжёра|задаче коммивояжёра]] длина входа почти пропорциональна количеству городов и дорог между ними), а под размером выхода — длина описания решения задачи (наилучшего маршрута в задаче коммивояжёра). | '''Вычисли́тельная сло́жность''' — понятие в [[информатика|информатике]] и [[теория алгоритмов|теории алгоритмов]], обозначающее функцию зависимости объёма работы, которая выполняется некоторым алгоритмом, от размера входных данных. Раздел, изучающий вычислительную сложность, называется [[Теория сложности вычислений|теорией сложности вычислений]]. Объём работы обычно измеряется [[абстракция|абстрактными]] понятиями времени и пространства, называемыми [[Вычислительные ресурсы|вычислительными ресурсами]]. Время определяется количеством элементарных шагов, необходимых для решения задачи, тогда как пространство определяется объёмом памяти или места на [[носитель информации|носителе данных]]. Таким образом, в этой области предпринимается попытка ответить на центральный вопрос разработки алгоритмов: «как изменится время исполнения и объём занятой памяти в зависимости от размера входа?». Здесь под размером входа понимается длина описания данных задачи в [[бит]]ах (например, в [[задача коммивояжёра|задаче коммивояжёра]] длина входа почти пропорциональна количеству городов и дорог между ними), а под размером выхода — длина описания решения задачи (наилучшего маршрута в задаче коммивояжёра). | ||
Версия 21:27, 19 октября 2022
| Описание | Вычисли́тельная сло́жность — понятие в информатике и теории алгоритмов, обозначающее функцию зависимости объёма работы, которая выполняется некоторым алгоритмом, от размера входных данных. |
|---|---|
| Область знаний | Информатика |
| Авторы | |
| Поясняющее видео | |
| Близкие понятия | |
| Среды и средства для освоения понятия | Scratch, Snap!, Python |
Вычисли́тельная сло́жность — понятие в информатике и теории алгоритмов, обозначающее функцию зависимости объёма работы, которая выполняется некоторым алгоритмом, от размера входных данных. Раздел, изучающий вычислительную сложность, называется теорией сложности вычислений. Объём работы обычно измеряется абстрактными понятиями времени и пространства, называемыми вычислительными ресурсами. Время определяется количеством элементарных шагов, необходимых для решения задачи, тогда как пространство определяется объёмом памяти или места на носителе данных. Таким образом, в этой области предпринимается попытка ответить на центральный вопрос разработки алгоритмов: «как изменится время исполнения и объём занятой памяти в зависимости от размера входа?». Здесь под размером входа понимается длина описания данных задачи в битах (например, в задаче коммивояжёра длина входа почти пропорциональна количеству городов и дорог между ними), а под размером выхода — длина описания решения задачи (наилучшего маршрута в задаче коммивояжёра).
