Как решать задачи за O(f) или o(f) в программировании?

Question

[Lici]

В ВУЗе (физика) было что-то на тему "О" большое и "О" малое, но это было изучено очень поверхностно. Теперь вижу, что это нужно в IT.

Что оно такое, как его узнать и почему все хотят решать задачи за менее, чем О(f) ?

Answer 1

[Calc]

1) АЛГОРИТМЫ
ПОСТРОЕНИЕ И АНАЛИЗ
Thomas H. Cormen
Charles E. Leiserson
Ronald L. Rivest
Clifford Stein
2) чем меньше итераций цикла (циклов) в задаче, тем меньше времени уходит на ее выполнение.
Пример
имеем отсортированный массив
в нем нужно найти 17
Есть выбор: Прямой перебор или двоичный поиск

Answer 2

[yttrium]

Речь идет об асимптотической или вычислительной сложности
википедия

самый быстрый алгоритм это когда его асимптотическая сложность = O(1)

Это не физика, это математика.

Comments

[Lici]

Было на курсе ММФ вроде. У меня на первых курсах было много матана (физик-ядерщин).

[yttrium]

ок. не учился на ядерщика (: