Каково общее время выполнения следующего кода (N — переменная типа int)

Я готовлюсь к экзамену, где я пришел к этому вопросу:

Каково общее время выполнения следующего кода (N — переменная типа int)

Z z = new Z(N);
for (int i = 0; i < N; i++) z.insert("Bob", i);

Класс Z:

public class Z
{
     String[] names;
     Integer[] numbers;
     int N = 0;

     public Z(int cap)
     {
        names = new String[cap];
        numbers = new Integer[cap];
     }


     public Integer find(String S)
     {
        for (int i = 0; i < N; i++)
        {
            if (names[i].equals(S)) return numbers[i];
        }
        return null;
     }

    public void insert(String S, Integer M)
    {
        for (int i = 0; i < N; i++)
        {
            if (names[i].equals(S)) numbers[i] = M;
        }
        names[N] = S;
        numbers[N] = M;
        N++;
    }
}

Я думаю, что ответ на этот вопрос - O (n ^ 2). Первый цикл for занимает O(n) раз, а метод insert занимает O(n) раз (обратите внимание: n++ при каждом вызове вставки), что в сумме дает O(n^2)


algorithm cumulative-sum time-complexity
person leshkari    schedule 28.05.2016    source источник
comment
Вы не можете рассчитать время работы, вы можете найти только прирост времени работы. Вы не можете преобразовать нотацию Big-O во время, это просто невозможно.   -  person Lasse V. Karlsen    schedule 28.05.2016

Ответы (1)


arrow_upward
0
arrow_downward

Во-первых, обратите внимание, что переменная N в основной части не совпадает с переменной N, на которую ссылается экземпляр объекта.

После создания объекта z его закрытый элемент N равен 0 и увеличивается только при каждом вызове insert.

Таким образом, количество итераций цикла в методе insert равно количеству предыдущих вызовов метода insert.

Таким образом, общее число итераций, выполненных в методе insert (со всеми вызовами N вместе), составляет:

Σi=0..N-1 (i)

Это равно:

½N(N-1)

что равно ½N² - ½N и, следовательно, O(n²)

person trincot    schedule 28.05.2016