Алгоритм проектирования ручного решения ошибки?

Question

Я читал о записи Big O из многих источников, включая Skiena и запись Wikipedia , раздел Example , в котором говорится:

При обычном использовании формальное определение нотации O не используется напрямую;скорее, обозначение O для функции f (x) получено по следующим правилам упрощения:

• Если f (x) является суммой нескольких членов, один из которых имеет наибольший ростставка сохраняется, а все остальные опускаются.

• Если f (x) является продуктом нескольких факторов, любые constants (термины в продукте, которые не зависят от x)omitted.

Решение - , задача 2.2 - O ((n ^ 3) / 3).Не следует ли опустить "/ 3" или я что-то упустил?

Answer 1

Не должен , положительные постоянные коэффициенты допускаются в О-нотации. Они просто бессмысленны и поэтому следует опустить.

Answer 2

Константы не нужно опускать, они просто не несут никакой информации - O (n ^ 3) совпадает с O (n ^ 3/3). Вы заметите, что цитируемый отрывок обсуждает типичное использование, а не строгие требования.

Глядя на конкретный ответ, решение асимптотически эквивалентно n ^ 3 / 3. Хотя формально оно ничем не отличается от O (n ^ 3), я предполагаю, что идея состоит в том, чтобы предоставить более конкретную информацию, задав O ( n ^ 3/3).

Answer 3

Вы правы.1/3 является константой, поэтому ее следует опустить.

Answer 4

Вы правы, чтобы быть правдивым, O (n ^ 3/3) (то есть O (1/3 * n ^ 3)) следует исключить коэффициент 1/3 из окончательного ответа. Это потому, что 1/3 компонента выражения тривиальна с чрезвычайно большим n. Это была бы хорошая возможность отредактировать Википедию и внести исправления.

Answer 5

Позвольте мне привести пример.

suppose we have function,
                f(n)=1/3 * (4n^3) + 4n^2+ 1


 lets gather all the facts...

 we know that , 
          for all sufficient large value of n>=1              
              1/3 * (4n^3) <= 1/3 *  4n^3

          for all sufficient large value of n>=1
               4n^2 <= 1/3 * 12n^3

      and similarly, for all sufficent large value of n>=1
                  1 <= 1/3 * 5n^3

  thus we can conclude that,                  
   1/3 * (4n^3) + 4n^2+ 1  <= 1/3 * 4n^3 + 1/3 * 12n^3+1/3 * 5n^3   , where n >=1

  lets simplify it,   
           1/3 * (4n^3) + 4n^2+ 1  <= (1/3) * 21n^3  
                            f(n)   <= (1/3) * 21n^3 
                            f(n)   <= ((1/3)*21)*n^3
                            f(n)   <= (7)*n^3    
                            f(n)   = O(n^3) , where c=7 and n0=1

 if we don't include 1/3 in c than, 
                            f(n)   <= (1/3) * 21n^3
                            f(n)   <=  (21)*(n^3 /3)
                            f(n)   = O(n^3 /3), where c=21 and n0=1

 so the constant value 'c' will be changed.