Вычислительная сложность: различия между версиями
Материал из Поле цифровой дидактики
Patarakin (обсуждение | вклад) (Новая страница: «{{Понятие |Field_of_knowledge=Информатика |Environment=Scratch, Snap!, Python }} '''Вычисли́тельная сло́жность''' — понятие в информатике и теории алгоритмов, обозначающее функцию зависимости объёма работы, которая выполняется некоторым алго...») |
Patarakin (обсуждение | вклад) |
||
| (не показана 1 промежуточная версия этого же участника) | |||
| Строка 1: | Строка 1: | ||
{{Понятие | {{Понятие | ||
|Description=Вычисли́тельная сло́жность — понятие в информатике и теории алгоритмов, обозначающее функцию зависимости объёма работы, которая выполняется некоторым алгоритмом, от размера входных данных. | |||
|Field_of_knowledge=Информатика | |Field_of_knowledge=Информатика | ||
|Environment=Scratch, Snap!, Python | |Environment=Scratch, Snap!, Python | ||
}} | }} | ||
'''Вычисли́тельная сло́жность''' — понятие в [[информатика|информатике]] и [[теория алгоритмов|теории алгоритмов]], обозначающее функцию зависимости объёма работы, которая выполняется некоторым алгоритмом, от размера входных данных. Раздел, изучающий вычислительную сложность, называется [[Теория сложности вычислений|теорией сложности вычислений]]. Объём работы обычно измеряется [[абстракция|абстрактными]] понятиями времени и пространства, называемыми [[Вычислительные ресурсы|вычислительными ресурсами]]. Время определяется количеством элементарных шагов, необходимых для решения задачи, тогда как пространство определяется объёмом памяти или места на [[носитель информации|носителе данных]]. Таким образом, в этой области предпринимается попытка ответить на центральный вопрос разработки алгоритмов: «как изменится время исполнения и объём занятой памяти в зависимости от размера входа?». Здесь под размером входа понимается длина описания данных задачи в [[бит]]ах (например, в [[задача коммивояжёра|задаче коммивояжёра]] длина входа почти пропорциональна количеству городов и дорог между ними), а под размером выхода — длина описания решения задачи (наилучшего маршрута в задаче коммивояжёра). | '''Вычисли́тельная сло́жность''' — понятие в [[информатика|информатике]] и [[теория алгоритмов|теории алгоритмов]], обозначающее функцию зависимости объёма работы, которая выполняется некоторым алгоритмом, от размера входных данных. Раздел, изучающий вычислительную сложность, называется [[Теория сложности вычислений|теорией сложности вычислений]]. Объём работы обычно измеряется [[абстракция|абстрактными]] понятиями времени и пространства, называемыми [[Вычислительные ресурсы|вычислительными ресурсами]]. Время определяется количеством элементарных шагов, необходимых для решения задачи, тогда как пространство определяется объёмом памяти или места на [[носитель информации|носителе данных]]. Таким образом, в этой области предпринимается попытка ответить на центральный вопрос разработки алгоритмов: «как изменится время исполнения и объём занятой памяти в зависимости от размера входа?». Здесь под размером входа понимается длина описания данных задачи в [[бит]]ах (например, в [[задача коммивояжёра|задаче коммивояжёра]] длина входа почти пропорциональна количеству городов и дорог между ними), а под размером выхода — длина описания решения задачи (наилучшего маршрута в задаче коммивояжёра). | ||
=== Примеры === | |||
* '''«почистить ковёр пылесосом»''' требует время, линейно зависящее от его площади (<math>\Theta(A)</math>), то есть на ковёр, площадь которого больше в два раза, уйдет в два раза больше времени. Соответственно, при увеличении площади ковра в сто тысяч раз объём работы увеличивается [[Пропорция (математика)|строго пропорционально]] в сто тысяч раз, и т. п. | |||
* '''«найти имя в телефонной книге»''' требует всего лишь времени, [[логарифм]]ически зависящего от количества записей (<math>O(\log_2(n))</math>), так как, открыв книгу примерно в середине, мы уменьшаем размер «оставшейся проблемы» вдвое (за счет сортировки имен по алфавиту). Таким образом, в книге объёмом в 1000 страниц любое имя находится не больше, чем за <math>\log_2 1000 \approx 10</math> раз (открываний книги). При увеличении объёма страниц до ста тысяч проблема все ещё решается за <math>\log_2 100000 \approx 17</math> заходов. (См. [[Двоичный поиск]].) | |||
Текущая версия на 21:28, 19 октября 2022
| Описание | Вычисли́тельная сло́жность — понятие в информатике и теории алгоритмов, обозначающее функцию зависимости объёма работы, которая выполняется некоторым алгоритмом, от размера входных данных. |
|---|---|
| Область знаний | Информатика |
| Авторы | |
| Поясняющее видео | |
| Близкие понятия | |
| Среды и средства для освоения понятия | Scratch, Snap!, Python |
Вычисли́тельная сло́жность — понятие в информатике и теории алгоритмов, обозначающее функцию зависимости объёма работы, которая выполняется некоторым алгоритмом, от размера входных данных. Раздел, изучающий вычислительную сложность, называется теорией сложности вычислений. Объём работы обычно измеряется абстрактными понятиями времени и пространства, называемыми вычислительными ресурсами. Время определяется количеством элементарных шагов, необходимых для решения задачи, тогда как пространство определяется объёмом памяти или места на носителе данных. Таким образом, в этой области предпринимается попытка ответить на центральный вопрос разработки алгоритмов: «как изменится время исполнения и объём занятой памяти в зависимости от размера входа?». Здесь под размером входа понимается длина описания данных задачи в битах (например, в задаче коммивояжёра длина входа почти пропорциональна количеству городов и дорог между ними), а под размером выхода — длина описания решения задачи (наилучшего маршрута в задаче коммивояжёра).
Примеры
- «почистить ковёр пылесосом» требует время, линейно зависящее от его площади ([math]\displaystyle{ \Theta(A) }[/math]), то есть на ковёр, площадь которого больше в два раза, уйдет в два раза больше времени. Соответственно, при увеличении площади ковра в сто тысяч раз объём работы увеличивается строго пропорционально в сто тысяч раз, и т. п.
- «найти имя в телефонной книге» требует всего лишь времени, логарифмически зависящего от количества записей ([math]\displaystyle{ O(\log_2(n)) }[/math]), так как, открыв книгу примерно в середине, мы уменьшаем размер «оставшейся проблемы» вдвое (за счет сортировки имен по алфавиту). Таким образом, в книге объёмом в 1000 страниц любое имя находится не больше, чем за [math]\displaystyle{ \log_2 1000 \approx 10 }[/math] раз (открываний книги). При увеличении объёма страниц до ста тысяч проблема все ещё решается за [math]\displaystyle{ \log_2 100000 \approx 17 }[/math] заходов. (См. Двоичный поиск.)
