Камянецкий. Избранное

🔶 Алгоритмы! Давайте поговорим про эффективность алгоритмов!



Что такое эффективный алгоритм? Быть может тот, который выполняется быстрее всего 🤷‍♂️



Рассмотрим задачу: В массивe из size элементов. Нужно найти максимальную сумму из m подряд идущих элeментов.



Пример 1: size = 10, m = 3,

array = { 4 5 0 [7 4 4] 6 2 6 3 }

max_sum = 15



Пример 2: size = 20, m = 5,

array = { 7 8 4 8 3 4 3 1 [7 7 8 9 9] 0 7 9 8 8 1 5 }

max_sum = 40



Как можно решать?



Первый способ — на мой взгляд, самый неэффективный



Найти все трёхэлементные суммы, затем среди них найти максимальный элемент. То есть



int m = ...

int[] array = ...



int[] sums = new int[size - m + 1];



for (int i = 0; i <= size - m; i++)

{

int t = 0;

for (int j = i; j < i + m;j++) t += array[j];

sums[i] = t;

}



int max = sums[0];

for (int i = 0; i < sums1.Length; i++)

{

if (sums[i] > max) max = sums[i];

}



Второй способ — хороший (как может показаться), но на деле не отличающийся от первого по времени, но лучше по используемым ресурсам:

Искать суммы очередных m элементов и сравнивать с ранее найденной суммой





int max = 0;

for (int i = 0; i <= size - m; i++)

{

int t = 0;

for (int j = i; j < i + m; j++)

{

t += array[j];

}

if (t > max) max = t;

}





Третий — на мой взгляд, самый хороший:

Найти сумму первых m элементов



int max = 0;

for (int i = 0; i < m; i++) max += array[i];



Затем вычитать из полученной суммы первый элемент, входящий в сумму и добавлять следующий по порядку, сравнивая текущую сумму с ранее найденной:



int temp = max;

for (int i = 1; i <= size - m; i++)

{

temp = temp - array[i - 1] + array[i + (m - 1)];

if (temp > max) max = temp;

}



Например, результаты поиска максимальной суммы по времени на каком-то компьютере могут выглядеть так:



для size = 1 000 000 и m = 3

Способ 1: 14 ms

Способ 2: 5 ms

Способ 3: 2 ms



для size = 1 000 000 и m = 5 000

Способ 1: 5 679 ms

Способ 2: 5 696 ms

Способ 3: 2 ms



для size = 1 000 000 и m = 10 000

Способ 1: 11 339 ms

Способ 2: 11 240 ms

Способ 3: 2 ms



для size = 1 000 000 и m = 100 000

Способ 1: 103 155 ms

Способ 2: 103 239 ms

Способ 3: 2 ms



для size = 1 000 000 и m = 250 000

Способ 1: 215 566 ms

Способ 2: 214 921 ms

Способ 3: 2 ms



PS про память не говорил, так как понятно, что первому способу всегда нужно больше всего.



🤔 Так что же такое эффективный алгоритм?



Исходник на github



#алгоритмы #csharp