Что такое O(N^2) при описании скорости работы алгоритма?

Ответы:

«O» большое и «o» малое (O и o) — математические обозначения для сравнения асимптотического поведения функций. Используются в различных разделах математики, но активнее всего — в математическом анализе, теории чисел и комбинаторике, а также при оценке сложности алгоритмов. В частности, фраза «сложность алгоритма есть O(n!)» означает, что при больших n время работы алгоритма (или общее количество операций) не более чем C · n!, где C — некая положительная константа (обычно в качестве параметра n берут объём входной информации алгоритма).

Без имени

N - размер исходных данных. Например, если речь идёт об алгоритме сортировки, то N - количество элементов массива.
N^2 - конечно же, квадрат.
Выражение "некоторая функция f(N) является О-большим от N^2" означает, что есть такая константа C, что |f(N)| <= |C*N^2|. То есть функция возрастает не быстрее, чем квадрат (помноженный на константу, но эта константа редко кого волнует).

15 лет назад

RPI.su - самая большая русскоязычная база вопросов и ответов. Наш проект был реализован как продолжение популярного сервиса otvety.google.ru, который был закрыт и удален 30 апреля 2015 года. Мы решили воскресить полезный сервис Ответы Гугл, чтобы любой человек смог публично узнать ответ на свой вопрос у интернет сообщества.

Все вопросы, добавленные на сайт ответов Google, мы скопировали и сохранили здесь. Имена старых пользователей также отображены в том виде, в котором они существовали ранее. Только нужно заново пройти регистрацию, чтобы иметь возможность задавать вопросы, или отвечать другим.

Чтобы связаться с нами по любому вопросу О САЙТЕ (реклама, сотрудничество, отзыв о сервисе), пишите на почту [email protected]. Только все общие вопросы размещайте на сайте, на них ответ по почте не предоставляется.