Почему Big O обозначения для следующих кодов, как это? - PullRequest
Новая
       11

Почему Big O обозначения для следующих кодов, как это?

2 голосов
/ 18 апреля 2020

Вопрос 1.

Мой ответ: 1 + n ^ 2 * n = n ^ 3

Правильный ответ: O (n) 

void f(int n) {
    if (n<1000000)
         return 0;
    for (int i=0; i<(n*n); i++)
         return f(n-1);
}

Вопрос 2 .

Мой ответ: n * n * logn = n ^ 2 * logn

Правильный ответ: O (n ^ 3) 

int f(int n) {
    for (int i=1; i< (n/2); i++) 
        for(double j =0; j <100; j+= (100.0/n) 
              doSomething (n/2); //doSomething(m) has time complexity of O(m)
    return 0;
}

Вопрос 3.

Мой ответ: 1 + n * (logn + 1) = O (nlogn)

Правильный ответ: O (logn) 

int f(n) {
    if (n<1) return;
    g(n-1); 
}

void g(n) {
    f(n/2) 
    doOne(); // doOne has time complexity O(1)
}

1 Ответ

3 голосов
/ 18 апреля 2020

Вопрос 1 

void f(int n) {
    if (n<1000000)
         return 0;
    for (int i=0; i<(n*n); i++)
         return f(n-1);
}

for l oop вообще не зацикливается, потому что содержимое является оператором return, поэтому у вас есть максимум одна l oop итерация. Это означает, что вы можете упростить этот код до: 

void f(int n) {
    if (n<=0)
         return 0;
    return f(n-1);
}

(упрощено в отношении анализа O (n))

Здесь вы понимаете, почему это O(n) потому что он ведет обратный отсчет, пока не достигнет условия остановки рекурсии. Тот факт, что существует проверка «высокого» значения для n<100000, не имеет значения, когда вы вызываете его с чем-то вроде f(5*10^300);

Вопрос 2 

int f(int n) {
    for (int i=1; i< (n/2); i++) 
        for(double j =0; j <100; j+= (100.0/n) 
              doSomething (n/2); //doSomething(m) has time complexity of O(m)
    return 0;
}

Что касается анализа O(n), вы можете упростить некоторые строки: 

for (int i=1; i< (n/2); i++)

Это можно упростить до: 

for (int i=1; i<n; i++)

Следовательно, это O(n), как вы уже определили . 

for(double j =0; j <100; j+= (100.0/n)

Это можно упростить как: 

for(double j =0; j <1; j+= (1.0/n)    (divided by 100)
for(double j =0; j <n; j+= 1.0)       (multiplied by n)

И снова простой O(n) l oop. 

doSomething (n/2);

То есть определение O(n) утверждение.

Итак, всего у вас есть O(n)*O(n)*O(n), что составляет O(n^3).

Вопрос 3 

int f(n) {
    if (n<1) return;
    g(n-1); 
}

void g(n) {
    f(n/2) 
    doOne(); // doOne has time complexity O(1)
}

Не уверен, как вы получили O(n*log(n)) здесь, потому что проверяется не каждое значение n. На самом деле вы начинаете с n и выполняете следующие шаги: n/2, n/4, n/8, n/16, n/32, n/64, n/128, ... и в какой-то момент вы достигли прекратить условие if (n<1). Это просто O(log(n)) l oop.

...