Понимание Big O для возведения в квадрат элементов в массиве - PullRequest
Новая
       59

Понимание Big O для возведения в квадрат элементов в массиве

0 голосов
/ 07 февраля 2019

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

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

Я пытаюсь понять большой O для моего кода и для кода, который был дан в решении.

Это мой код 

def sortedSquare(A):
    new_A = []
    for num in A:
        num = num*num
        new_A.append(num)
    return sorted(new_A)


print(sortedSquare([-4, -1, 0, 3, 10]))

Вот код решения: 

def sortedSquares(self, A):
    return sorted(x*x for x in A)

Для решения Big O равен 

NlogN

Где N - длина массива.Я не понимаю, почему это будет logN, а не просто N для Big O?

Для моего решения я вижу его как Big O of N, потому что я просто перебираю весь массив.

Кроме того, мое решение является хорошим решением по сравнению с решением, которое было дано?

Ответы [ 3 ]

0 голосов
/ 07 февраля 2019

Сложность работает так, что общая сложность для всей программы является наихудшей сложностью для любой части.Итак, в вашем случае у вас есть часть, которая возводит числа в квадрат, и у вас есть часть, которая сортирует числа.Итак, какая часть определяет общую сложность?

Квадратная часть - это o (n), потому что вы только касаетесь элементов один раз, чтобы их возвести в квадрат.

Как насчет сортирующей части?Обычно это зависит от того, какую функцию сортировки вы используете:

  • Большинство процедур сортировки имеют O (n * log (n)), потому что они используют алгоритм «разделяй и властвуй».
  • Некоторые (например,пузырьковая сортировка) имеют O (n ^ 2)
  • Некоторые (например, счетная сортировка) имеют O (n)

В вашем случае говорят, что данное решение является O (n * log (n)) и поскольку квадратная часть равна O (n), то сортирующая часть должна быть O (n * log (n)).И так как ваш код использует ту же функцию сортировки, что и данное решение, ваша сортировка также должна быть O (n * log (n))

Таким образом, ваша квадратичная часть - O (n), а ваша сортирующая часть - O (n* log (n)), и общая сложность является худшей из них: O (n * log (n))

0 голосов
/ 07 февраля 2019

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

Квадрат всех элементов (O (N)) и обратная отрицательная подпоследовательность (O (N) в худшем случае), так что обе последовательности отсортированы.Если одна из подпоследовательностей пуста, все готово.

В противном случае объедините две последовательности за время O (N) (этот шаг использует дополнительное пространство O (N)).

0 голосов
/ 07 февраля 2019

Ваше решение делает то же самое, что и данное решение.Оба решения возводят в квадрат все элементы, а затем сортируют результирующий массив, причем решение leetcode немного более кратко.

Причина, по которой оба эти решения равны O(NlogN), заключается в использовании sorted().Встроенная сортировка Python - timsort , которая сортирует массив в O(NlogN) времени.* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *] * * * * * * * * * * * * * * * * * * * * * * ”* '*' * '*' 101 '*' * 1011 '* * * * * * * * * *

.шаг слияния в сортировке слияния.

Редактировать:

Дэвид Эйзенстат поднял очень хороший момент на Тимсорте.Timsort агрегирует строго возрастающие и строго убывающие пробеги и объединяет их.Поскольку результирующий квадратный массив будет сначала строго уменьшаться, а затем строго увеличиваться, timsort на самом деле полностью меняет строго убывающий прогон, а затем объединяет их в O(N).

...