2023-01-09 08:47:14
Алгоритмы! Давайте поговорим про эффективность алгоритмов!
Что такое эффективный алгоритм? Быть может тот, который выполняется быстрее всего
Рассмотрим задачу: В массив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
833 views05:47
I
