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

Patarakin в 12:41, 1 декабря 2022

2022-12-01T12:41:49Z

← Предыдущая версия		Версия от 15:41, 1 декабря 2022
Строка 12:		Строка 12:
	\| константное время \|\| Определение чётности целого числа (представленного в двоичном виде)		\| константное время \|\| Определение чётности целого числа (представленного в двоичном виде)
	\|-		\|-
	\| \|\|		\| логарифмическое время \|\| [[Двоичный поиск]]
	\|-		\|-
	\| \|\|		\| линейное время \|\| Поиск наименьшего или наибольшего элемента в неотсортированном [[массив]]е
	\|-		\|-
	\| \|\|		\| экспоненциальное время<br>(с линейной экспонентой) \|\| Решение [[Задача коммивояжёра\|задачи коммивояжёра]] с помощью [[Динамическое программирование\|динамического программирования]]
	\|-		\|-
	\| \|\|		\| экспоненциальное время \|\|
	\|-		\|-
	\| \|\|		\| факториальное время \|\|
	\|-
	\| \|\|
	\|}		\|}

Patarakin в 12:37, 1 декабря 2022

2022-12-01T12:37:09Z

← Предыдущая версия		Версия от 15:37, 1 декабря 2022
Строка 5:		Строка 5:
	}}		}}
	Временная сложность алгоритма обычно выражается с использованием [[Big O notation\|нотации «O» большое]], которая учитывает только слагаемое самого высокого порядка, а также не учитывает константные множители, то есть коэффициенты. Временная сложность обычно оценивается путём подсчёта числа элементарных операций, осуществляемых алгоритмом. Время исполнения одной такой операции при этом берётся константой, то есть асимптотически оценивается как O(1). В таких обозначениях полное время исполнения и число элементарных операций, выполненных алгоритмом, отличаются максимум на постоянный множитель, который не учитывается в O-нотации.		Временная сложность алгоритма обычно выражается с использованием [[Big O notation\|нотации «O» большое]], которая учитывает только слагаемое самого высокого порядка, а также не учитывает константные множители, то есть коэффициенты. Временная сложность обычно оценивается путём подсчёта числа элементарных операций, осуществляемых алгоритмом. Время исполнения одной такой операции при этом берётся константой, то есть асимптотически оценивается как O(1). В таких обозначениях полное время исполнения и число элементарных операций, выполненных алгоритмом, отличаются максимум на постоянный множитель, который не учитывается в O-нотации.

			{\| class="wikitable"
			\|-
			! Название !! Примеры алгоритмов
			\|-
			\| константное время \|\| Определение чётности целого числа (представленного в двоичном виде)
			\|-
			\| \|\|
			\|-
			\| \|\|
			\|-
			\| \|\|
			\|-
			\| \|\|
			\|-
			\| \|\|
			\|-
			\| \|\|
			\|}

Patarakin в 12:08, 1 декабря 2022

2022-12-01T12:08:55Z

← Предыдущая версия		Версия от 15:08, 1 декабря 2022
Строка 1:		Строка 1:
	{{Понятие		{{Понятие
	\|Description=В информатике временна́я сложность алгоритма определяется как функция от длины строки, представляющей входные данные, равная времени работы алгоритма на данном входе.		\|Description=В информатике временна́я сложность алгоритма определяется как функция от длины строки, представляющей входные данные, равная времени работы алгоритма на данном входе.
			\|Field_of_knowledge=Информатика
			\|Environment=R, J, Python, Snap!
	}}		}}
	Временная сложность алгоритма обычно выражается с использованием [[Big O notation\|нотации «O» большое]], которая учитывает только слагаемое самого высокого порядка, а также не учитывает константные множители, то есть коэффициенты. Временная сложность обычно оценивается путём подсчёта числа элементарных операций, осуществляемых алгоритмом. Время исполнения одной такой операции при этом берётся константой, то есть асимптотически оценивается как O(1). В таких обозначениях полное время исполнения и число элементарных операций, выполненных алгоритмом, отличаются максимум на постоянный множитель, который не учитывается в O-нотации.		Временная сложность алгоритма обычно выражается с использованием [[Big O notation\|нотации «O» большое]], которая учитывает только слагаемое самого высокого порядка, а также не учитывает константные множители, то есть коэффициенты. Временная сложность обычно оценивается путём подсчёта числа элементарных операций, осуществляемых алгоритмом. Время исполнения одной такой операции при этом берётся константой, то есть асимптотически оценивается как O(1). В таких обозначениях полное время исполнения и число элементарных операций, выполненных алгоритмом, отличаются максимум на постоянный множитель, который не учитывается в O-нотации.

Patarakin в 12:08, 1 декабря 2022

2022-12-01T12:08:27Z

← Предыдущая версия		Версия от 15:08, 1 декабря 2022
Строка 2:		Строка 2:
	\|Description=В информатике временна́я сложность алгоритма определяется как функция от длины строки, представляющей входные данные, равная времени работы алгоритма на данном входе.		\|Description=В информатике временна́я сложность алгоритма определяется как функция от длины строки, представляющей входные данные, равная времени работы алгоритма на данном входе.
	}}		}}
	Временная сложность алгоритма обычно выражается с использованием [[Big O notation\|нотации «O» большое]], которая учитывает только слагаемое самого высокого порядка, а также не учитывает константные множители, то есть коэффициенты. Временная сложность обычно оценивается путём подсчёта числа элементарных операций, осуществляемых алгоритмом. Время исполнения одной такой операции при этом берётся константой, то есть асимптотически оценивается как ~~{\displaystyle O(1)}~~O(1). В таких обозначениях полное время исполнения и число элементарных операций, выполненных алгоритмом, отличаются максимум на постоянный множитель, который не учитывается в O-нотации.		Временная сложность алгоритма обычно выражается с использованием [[Big O notation\|нотации «O» большое]], которая учитывает только слагаемое самого высокого порядка, а также не учитывает константные множители, то есть коэффициенты. Временная сложность обычно оценивается путём подсчёта числа элементарных операций, осуществляемых алгоритмом. Время исполнения одной такой операции при этом берётся константой, то есть асимптотически оценивается как O(1). В таких обозначениях полное время исполнения и число элементарных операций, выполненных алгоритмом, отличаются максимум на постоянный множитель, который не учитывается в O-нотации.

Patarakin: Новая страница: «{{Понятие |Description=В информатике временна́я сложность алгоритма определяется как функция от длины строки, представляющей входные данные, равная времени работы алгоритма на данном входе. }} Временная сложность алгоритма обычно выражается с использовани...»

2022-12-01T12:03:18Z

Новая страница: «{{Понятие |Description=В информатике временна́я сложность алгоритма определяется как функция от длины строки, представляющей входные данные, равная времени работы алгоритма на данном входе. }} Временная сложность алгоритма обычно выражается с использовани...»

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

{{Понятие
|Description=В информатике временна́я сложность алгоритма определяется как функция от длины строки, представляющей входные данные, равная времени работы алгоритма на данном входе.
}}
Временная сложность алгоритма обычно выражается с использованием [[Big O notation|нотации «O» большое]], которая учитывает только слагаемое самого высокого порядка, а также не учитывает константные множители, то есть коэффициенты. Временная сложность обычно оценивается путём подсчёта числа элементарных операций, осуществляемых алгоритмом. Время исполнения одной такой операции при этом берётся константой, то есть асимптотически оценивается как {\displaystyle O(1)}O(1). В таких обозначениях полное время исполнения и число элементарных операций, выполненных алгоритмом, отличаются максимум на постоянный множитель, который не учитывается в O-нотации.