Большая O-нотация дает вам сложность алгоритма в худшем случае, и в основном полезно знать, как алгоритм будет расти во время выполнения, когда количество данных, которые должны обрабатываться, увеличивается. Например (синтаксис в стиле C, это не важно):
List<int> ls = new List<int>(); (1) O(1)
for (int i = 0; i < ls.count; i++) (2) O(1)
foo(i); (3) O(log n) (efficient function)
Cost analysis:
(1) cost: O(1), constant cost
(2) cost: O(1), (int i = 0;)
O(1), (i < ls.count)
O(1), (i++)
---- total: O(1) (constant cost), but it repeats n times (ls.count)
(3) cost: O(log n) (assume it, just an example),
but it repeats n times as it is inside the loop
Таким образом, в асимптотической записи это будет стоить: O(n log n) (не так эффективно), что в данном примере является разумным результатом, но возьмем этот пример:
List<int> ls = new List<int>(); (1) O(1)
for (int i = 0; i < ls.count; i++) (2) O(1)
if ( (i mod 2) == 0) ) (*) O(1) (constant cost)
foo(i); (3) O(log n)
Тот же алгоритм, но с новой строкой с условием. В этом случае асимптотическая нотация выберет наихудший случай и даст те же результаты, что и выше O(n log n), когда легко обнаружить, что шаг (3) будет выполняться только в половине раз.
Данные и так являются только примерами и могут быть неточными, просто пытаясь проиллюстрировать поведение записи Big O. Это в основном дает вам поведение вашего алгоритма, когда данные растут (ваш алгоритм будет линейным, экспоненциальным, логарифмическим, ...), но это не то, что все знают как «эффективность», или почти, это не единственный » эффективность "смысл.
Однако этот метод может обнаружить алгоритмы «невозможного процесса» (извините, не знаю точного английского слова), то есть алгоритмы, которые потребуют гигантского количества времени для обработки на ранних этапах (подумайте в факториалы, например, или очень большой матикс).
Если вы хотите провести исследование эффективности в реальном мире, возможно, вы предпочитаете собирать какие-то данные из реального мира и делать реальный эталон поведения вашего алгоритма с этими данными. Это не математический стиль, но он будет более точным в большинстве случаев (но не в худшем случае!;)).
Надеюсь, это поможет.