Почему это O (nlogn)

Question

Сегодня у меня было стажировочное интервью, и я не мог понять это.

total = 0 

product(int array[]) { 

    if (array.length == 1) { 
     return array[0] 
    } else { 
     product(product right side array * product left side) 
    } 
} 

Answer 1

product(left side) * product(right side) собирается вернуть единственное число, так что внешний вызов product собирается принять O (1).

Два внутренних вызова просто выполняют двоичную древовидную глубину - сначала проходят через массив, и это занимает время O (n).

Однако на каждом уровне ходьбы он выполняет внешний вызов product, и есть уровни O (logn), и на каждом уровне стоимость O (1), поэтому умножает усилие на O (logn), поэтому вы получаете O (nlogn).

Answer 2

Это O (N log N), поскольку количество копий каждого значения равно O (log N).

Представьте, что у вас несколько уровней. На первом уровне N элементов в одном массиве, на втором уровне N/2 элементов в 2 массивах, на третьем уровне N/4 элементов в 4 массивах и т. Д. До тех пор, пока у вас не будет 1 элемент в N массивах. Это берет log2 (n) уровней, чтобы идти сверху вниз. Каждое значение было скопировано log2 (N) раз, что означает, что временной сложностью является O (log (N) * N), поскольку база журнала не имеет значения.

Вы можете сказать, что другие операции, такие как * и new Array, стоят дороже, однако это O (N), а по мере того, как N растет только в случае более высоких заказов.

Answer 3

Причина в том, что когда массив имеет длину 1, время является постоянным, а если оно имеет длину n, то используются 2 рекурсивных вызова с половиной массива.

Немного более формально, используя индукцию по длине n массива. В базовом случае малый размер массива равен 1, и, очевидно, количество операций является константой (это соответствует O (nlog n) ... и все).

В общем индуктивного случае с длиной массива п, оба рекурсивные вызовы product right side array и product left side включают N/2 элементов (разделить массив в 2-х частей), и, следовательно, количество операций

н/2 (log n/2) + n/2 (log_2 n/2) = n/2 (log n -1) + n/2 (log n -1) = n log n -2.

В этом случае операция if рассчитывается как 1 дополнительная операция, а сам продукт * - еще один, что дает в общей сложности n log n, но добавление константы не имеет значения.

Вы также можете думать, что рекурсивные вызовы product(product right side array * product left side) имеют «глубину» log n (в случае, начиная с 256, «глубина» рекурсивных вызовов будет равна 8), так как каждый раз, когда размер array - это половина начальной. Так, наконец, п элементы возвращаются это дает O (N журнал (п))

Answer 4

Высота дерева рекурсии находится в наиболее log_2 п, потому что это количество раз, вы можете сократить вдвое п до достижения n = 1 (т. Е. Листовой узел) - подумайте о log_2 n как число бит в n.

Ширин каждого уровня дерева не более чем п (в нижней части, каждый элемент массива посещается ровно один раз, верхние уровни дерева, очевидно, более узкие).

В каждой ветви выполняется постоянное время (O (1)) операция умножения (предполагая для этого аргумента, что разделение массива является постоянным временем).

Следовательно, верхняя граница числа операций равна O (1) x n x log_2 n = O (n log n).