Зміст:
Визначення - Що означає складність часу?
Часова складність - це поняття в інформатиці, яке займається кількісним визначенням часу, затраченого набором коду або алгоритму на обробку або запуск як функцію від кількості вводу.
Іншими словами, часова складність - це по суті ефективність, або те, як триває функція програми для обробки заданого вводу.
Техопедія пояснює складність у часі
Часова складність - це просто міра часу, необхідного функції чи виразу, щоб виконати своє завдання, а також назва процесу для вимірювання цього часу. Він може застосовуватися майже до будь-якого алгоритму чи функції, але є більш корисним для рекурсивних функцій. Немає сенсу вимірювати часову складність для таких додатків, як отримання імені користувача та пароля з бази даних для порівняння або просто збереження даних, будь то 20 мс або 5 мс; це було б більше у лінії доступу. Це не має нічого спільного з турботою про час його виконання, а швидше, що різниця незначна. Однак якщо є рекурсивна функція, яку можна викликати кілька разів, визначення та розуміння джерела її часової складності може допомогти скоротити загальний час обробки з, скажімо, 600 мс до 100 мс.
Часова складність виражається, як правило, у "великій нотації O", але є й інші позначення. Це математичне подання верхньої межі коефіцієнта масштабування для алгоритму і записується як O (Nn), при цьому "N" - кількість входів, а "n" - кількість циклічних виразів. Наприклад, у нас є алгоритм:
numbers = {5, 6, 10, 11, 2}; foreach (number as number1)
{
foreach(number as number2)
{
statements; } }
numbers = {5, 6, 10, 11, 2};
foreach (number as number1)
{
foreach(number as number2)
{
statements; } }
numbers = {5, 6, 10, 11, 2};
foreach (number as number1)
{
foreach(number as number2) {
statements; } }
numbers = {5, 6, 10, 11, 2};
foreach (number as number1)
{
foreach(number as number2)
{
statements; } }
numbers = {5, 6, 10, 11, 2};
foreach (number as number1)
{
foreach(number as number2)
{
statements; } }
У масиві «цифр» є п’ять входів, а цикл «foreach» повторюється двічі. Тому експоненціальне зростання часу обробки відбувається в міру збільшення кількості входів і кількості циклів.
