Блог

Главная - Вопросы по программированию - Какую сложность имеет следующий алгоритм?

Какую сложность имеет следующий алгоритм?

#java #algorithm #time-complexity #big-o

#java #алгоритм #временная сложность #big-o

Вопрос:

Какова сложность следующего кода?

 public static int foo(int[] a){
        int[] b  = new int[a.length];

        for(int i = 0; i < a.length;   i){
            for(int j = 0; j < b.length / 100;   j ){
                b[i]  = a[i]   a[j];
            }
        }

        int result = 0;
        for(int i = 0; i < b.length; i   ){
            result  = b[i];
        }
        return resu<
   }

Комментарии:

1. Почему бы вам не рассказать нам , что вы думаете об этом (и почему), и тогда мы сможем исправить вас, если вы ошибаетесь?

2. O(a.length x b.length) O(b.length) обычно вы можете просто сказать, что это O(n^2) if a имеет размер n

Ответ №1:

 public static int foo(int[] a){
    // O(1)
    int[] b  = new int[a.length];

    // O(a.length x a .length)
    for(int i = 0; i < a.length;   i){
        // O(a.length)
        for(int j = 0; j < b.length / 100;   j ){
            b[i]  = a[i]   a[j];
        }
    }

    // O(1)
    int result = 0;

    // O(a.length)
    for(int i = 0; i < b.length; i   ){
        result  = b[i];
    }
    return resu<

}

Допустим a , имеет размер n , всего: O(n^2) O(n) = O(n^2)

Ответ №2:

Я думаю, что это будет:

 O(1)   O(n)*O(n/100)   O(n) = O(1)   O(n^2/100)   O(n)

Таким образом, общая сложность ~O(n^2)