Интересный, таким образом, сложный рекурсивный расчет Big-O - конкретные примеры - PullRequest
Новая
       22

Интересный, таким образом, сложный рекурсивный расчет Big-O - конкретные примеры

0 голосов
/ 19 ноября 2018

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

У задания для этой темы есть несколько действительно интересных сложных примеров с рекурсией, вызывающей друг друга и для циклов, в то время как циклыи т. д. ... что я не мог понять и нужна помощь в расчете.Я действительно ценю любую помощь и объяснение, чтобы глубоко понять это.

Также: Пример № 3: Я не понимаю, что означает возвращение "0xCAFE + 0xBABE + s"?Я не мог видеть, чтобы он где-то появлялся в методе, действительно странном для меня.

Пример № 4: Сначала я подумал, что это разные примеры, но я заметил, что в методе g есть вызов метода f, поэтомудолжно быть в одном примере, верно ли мое предположение?

1. 

long c(int x) {
    if (x <= 1) {
        return 1;
    } else {
        long s = 0;
        for (int i = 1; i < x; i++) {
            s = s + c(x - 1);
        }
        return s;
    }
}

2. 

long d(int x) {
    long s = -x * x;
    while (s <= x * x * x) {
        s++;
    }
    for (long i = s * x; i > 0; i--) {
        s--;
    }
    return s;
}

3. 

double e(long x, long y) {
    double s = 0_0;
    for (int i = 1; i <= x; i *= 2) {
        for (double j = x; j >= 1; j /= 3) {
            for (int k = 0; k < y; k += 4) {
                s++;
            }
        }
    }
    return 0xCAFE + 0xBABE + s;
}

4. Рассчитать каждый F & G 

long f(int x, int y) {
    if (x <= 0) {
        return y;
    } else {
        return f(x - 1, 2 * y);
    }
}

double g(int x, int y) {
    double s = 0.0D;
    for (long i = f(x, y); i >= 0; i--) {
        s++;
    }
    return s;
}

5. 

char h(int x) {
    char h = 'h';
    for (long i = h; i-- > ++i; x--) {
        h++;
    }
    return h;
}

1 Ответ

0 голосов
/ 19 ноября 2018

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

Небольшой пример: O (n) 

public void o(int n, int i) {
    if (i == n)
       return;

    o(n, i++);
}

Это похоже на цикл, 

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

В примере 3: 

return 0xCAFE + 0xBABE + s;

Произвольно, похоже, что оно ничего не представляет, и 's' будет большим значением O для сложности методов через их циклы, 

for (int i = 1; i <= x; i *= 2) { // BigO = 2 ^ i
    for (double j = x; j >= 1; j /= 3) {  // BigO = (2 ^i) / 3
        for (int k = 0; k < y; k += 4) {  //BigO = y / 4
...