Big O Notation Sumation confusion

Question

Я хочу использовать Big O Notation, чтобы убедить других в улучшении кода - как для эффективности, так и для читаемости. Но я не уверен, что я ошибаюсь.

Из Big O Notation я понимаю, что O (n) + O (n) = O (n) (приблизительный). Значит, постоянная впереди пренебрежимо мала.

Однако, принимая пример, скажем для цикла

//Case 1: One For-Loop - O(n) 
for(var i=0;i<n;i++) 
{ 
    doA(i); 
    doB(i); 
} 

Для лучшей читаемости, я предпочитаю писать таким образом:

//Case 2: Two For-Loop - O(n) + O(n) 
function doA(){ 
    for(var i=0;i<n;i++){ 
    //do logic A 
    } 
} 

function doB(){ 
    for(var i=0;i<n;i++){ 
     //do Logic B 
    } 
} 

Такое, что я могу не откладывая вызывающему

doA(); 
doB(); 

... без петли снаружи.

Теперь проблема в том, что я не могу убедить себя, ЕСЛИ это для цикла фактически занимает 10 секунд. Тогда O (n) + O (n) составляет фактически 20 секунд. Как можно сказать, что O (n) + O (n) приближенно-способно к O (n)

Answer 1

Как мы можем сказать, что O (n) + O (n) приближенно-способно к O (п)

Для вашего (университет) проблемы, там четыре типа сложности:

• логарифмические (O (журнал (п)))
• линейной (O (п))
• многочлен (О (п^к, к elemOf {1,2,3, ...}))
• экспоненциальный (О (п^п))

Ваш вопрос относится ко второму случаю:

InfinityO(n) + O(n)O(n), потому что оба являются линейными.
Таким образом, вы можете думать об этом как

linear + linear = linear 

Linear означает, что если вы удвоить объем ввода, время обработки удваивается.

В других, более медленных случаях количество времени обработки будет

• п^2, п^3, ... в случае полиномиальной сложности (Удвоение количество входных результатов в входе^2, входа^3 или ввода время 4 обработки ^)
• п^п (что Reall y большой/медленный) ... в случае экспоненциальная сложность (Умножение количества входных данных само по себе приводит к времени обработки, умноженному на себя, например.3 * 3 = 9, 4 * 4 = 16, 5 * 5 = 25 ...).