Вычислительная сложность - История изменений

Patarakin в 18:28, 19 октября 2022

2022-10-19T18:28:24Z

← Предыдущая версия		Версия от 21:28, 19 октября 2022
Строка 5:		Строка 5:
	}}		}}
	'''Вычисли́тельная сло́жность''' — понятие в [[информатика\|информатике]] и [[теория алгоритмов\|теории алгоритмов]], обозначающее функцию зависимости объёма работы, которая выполняется некоторым алгоритмом, от размера входных данных. Раздел, изучающий вычислительную сложность, называется [[Теория сложности вычислений\|теорией сложности вычислений]]. Объём работы обычно измеряется [[абстракция\|абстрактными]] понятиями времени и пространства, называемыми [[Вычислительные ресурсы\|вычислительными ресурсами]]. Время определяется количеством элементарных шагов, необходимых для решения задачи, тогда как пространство определяется объёмом памяти или места на [[носитель информации\|носителе данных]]. Таким образом, в этой области предпринимается попытка ответить на центральный вопрос разработки алгоритмов: «как изменится время исполнения и объём занятой памяти в зависимости от размера входа?». Здесь под размером входа понимается длина описания данных задачи в [[бит]]ах (например, в [[задача коммивояжёра\|задаче коммивояжёра]] длина входа почти пропорциональна количеству городов и дорог между ними), а под размером выхода — длина описания решения задачи (наилучшего маршрута в задаче коммивояжёра).		'''Вычисли́тельная сло́жность''' — понятие в [[информатика\|информатике]] и [[теория алгоритмов\|теории алгоритмов]], обозначающее функцию зависимости объёма работы, которая выполняется некоторым алгоритмом, от размера входных данных. Раздел, изучающий вычислительную сложность, называется [[Теория сложности вычислений\|теорией сложности вычислений]]. Объём работы обычно измеряется [[абстракция\|абстрактными]] понятиями времени и пространства, называемыми [[Вычислительные ресурсы\|вычислительными ресурсами]]. Время определяется количеством элементарных шагов, необходимых для решения задачи, тогда как пространство определяется объёмом памяти или места на [[носитель информации\|носителе данных]]. Таким образом, в этой области предпринимается попытка ответить на центральный вопрос разработки алгоритмов: «как изменится время исполнения и объём занятой памяти в зависимости от размера входа?». Здесь под размером входа понимается длина описания данных задачи в [[бит]]ах (например, в [[задача коммивояжёра\|задаче коммивояжёра]] длина входа почти пропорциональна количеству городов и дорог между ними), а под размером выхода — длина описания решения задачи (наилучшего маршрута в задаче коммивояжёра).

			=== Примеры ===
			* '''«почистить ковёр пылесосом»''' требует время, линейно зависящее от его площади (<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> заходов. (См. [[Двоичный поиск]].)

Patarakin в 18:27, 19 октября 2022

2022-10-19T18:27:34Z

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

Patarakin: Новая страница: «{{Понятие |Field_of_knowledge=Информатика |Environment=Scratch, Snap!, Python }} '''Вычисли́тельная сло́жность''' — понятие в информатике и теории алгоритмов, обозначающее функцию зависимости объёма работы, которая выполняется некоторым алго...»

2022-10-19T18:27:10Z

Новая страница: «{{Понятие |Field_of_knowledge=Информатика |Environment=Scratch, Snap!, Python }} '''Вычисли́тельная сло́жность''' — понятие в информатике и теории алгоритмов, обозначающее функцию зависимости объёма работы, которая выполняется некоторым алго...»

Новая страница

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