Временная сложность алгоритма: различия между версиями
Материал из Поле цифровой дидактики
Patarakin (обсуждение | вклад) |
Patarakin (обсуждение | вклад) |
||
| Строка 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-нотации. | ||
Версия 15:08, 1 декабря 2022
| Описание | В информатике временна́я сложность алгоритма определяется как функция от длины строки, представляющей входные данные, равная времени работы алгоритма на данном входе. |
|---|---|
| Область знаний | Информатика |
| Авторы | |
| Поясняющее видео | |
| Близкие понятия | |
| Среды и средства для освоения понятия | R, J, Python, Snap! |
Временная сложность алгоритма обычно выражается с использованием нотации «O» большое, которая учитывает только слагаемое самого высокого порядка, а также не учитывает константные множители, то есть коэффициенты. Временная сложность обычно оценивается путём подсчёта числа элементарных операций, осуществляемых алгоритмом. Время исполнения одной такой операции при этом берётся константой, то есть асимптотически оценивается как O(1). В таких обозначениях полное время исполнения и число элементарных операций, выполненных алгоритмом, отличаются максимум на постоянный множитель, который не учитывается в O-нотации.
