Какой символ в нотации Big O соответствует алгоритму с линейной временной сложностью? Выберите единственный правильный вариант.
Подробное объяснение
Линейная временная сложность означает, что время выполнения алгоритма увеличивается прямо пропорционально размеру входных данных n. В нотации Big O это обозначается как O(n), где n представляет количество операций, зависящих от размера входных данных. Например, простой перебор элементов массива имеет сложность O(n), так как каждый элемент обрабатывается один раз. Это один из основных классов сложности в анализе алгоритмов, наряду с константной O(1), логарифмической O(log n) и квадратичной O(n²).
Часто задаваемые вопросы (FAQ)
1
Что означает временная сложность O(1)?
O(1) обозначает константную временную сложность, когда время выполнения алгоритма не зависит от размера входных данных. Алгоритм выполняется за фиксированное время независимо от того, сколько данных ему передано.
2
Какой алгоритм имеет квадратичную сложность O(n²)?
Квадратичная сложность O(n²) характерна для алгоритмов, где время выполнения пропорционально квадрату размера входных данных. Типичный пример - алгоритмы с вложенными циклами, такие как пузырьковая сортировка или перебор всех пар элементов в массиве.
3
Чем отличается O(log n) от O(n)?
O(log n) - это логарифмическая сложность, которая растет гораздо медленнее, чем линейная O(n). Например, бинарный поиск имеет сложность O(log n), так как на каждом шаге он уменьшает область поиска вдвое, тогда как линейный поиск имеет сложность O(n), проверяя каждый элемент последовательно.
Типичные ошибки
1
Путаница между O(n) и O(1)
Некоторые ошибочно считают, что O(1) обозначает линейную сложность, но на самом деле O(1) - это константная сложность. Линейная сложность всегда обозначается как O(n), где время выполнения прямо пропорционально размеру входных данных.
2
Смешение O(n) с O(n²)
Учащиеся иногда путают линейную O(n) и квадратичную O(n²) сложности. Ключевое отличие: при удвоении размера входных данных время выполнения O(n) увеличивается примерно в 2 раза, а O(n²) - в 4 раза.
3
Неправильная интерпретация нотации Big O
Big O описывает верхнюю границу роста времени выполнения, а не точное время. O(n) означает, что алгоритм растет не быстрее, чем линейно, но может быть и быстрее для некоторых входных данных. Это асимптотическая оценка, а не точная формула времени выполнения.