Блог

Какова классификация BigO для этой функции?

Определение проблемы: У вас есть массив целых чисел, и вы хотите найти наибольшую непрерывную (вместе взятую в последовательности) промежуточную сумму. Найдите суммы всех смежных подмассивов и верните максимальное значение.

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

 def largest_contiguous_sub_sum(arr)
    largest_sum = -100

    (0...arr.length).each do |start_idx|
        (start_idx...arr.length).each do |end_idx|
            current_sum = arr[start_idx..end_idx].sum
            largest_sum = current_sum if largest_sum < current_sum
        end
    end
    largest_sum
end

arr = [2, 3, -6, 7, -6, 7] #=> 8

  

BigO касается не данных, которые вы просматриваете, а того, как вы выполняете итерации по этим данным. Я вижу три первичных цикла:

• от 0 до N как x
• из x в N в y
• из x в y в z

Для меня это выглядит как O ^ 3.

Вложенные циклы не обрабатывают одни и те же данные дважды

Они абсолютно такие. Даже не дважды.

Первая итерация внутреннего цикла от 0 до N. Затем от 1 до N. Затем всего от 2 до N. N итераций. Это делает ее O (N ^ 2). И это только явные циклы, не включая фактическую логику, которая имеет другое линейное сканирование.

что, несмотря на наличие вложенных циклов, эта функция по-прежнему имеет временную сложность O (n)

Это тривиально доказать. Измерьте время, необходимое вашей функции для выполнения на входных данных длиной N. Затем измерьте длину 10 * N. Если у нее линейная сложность во время выполнения, во второй раз она будет выполняться всего в 10 раз медленнее. Но в этом случае снижение производительности будет … более заметным.