Я имел дело с очень маленькими хранилищами данных, где действительно не имело значения, насколько я расточительно разбирал данные. Недавно я начал работать над хранилищем данных с записями в 100000-х годах и сейчас изучаю оптимизацию моих алгоритмов. Я просто сократил свое время в несколько сотен раз и пытался сравнить несколько других решений. У меня есть вопрос по терминологии:
Есть ли четко определенный способ, например, обозначение Big O, сказать: «Этот алгоритм занимает половину времени как этот алгоритм»?
Big O notation - это хорошо понятный кроссплатформенный способ определения временной сложности алгоритма с помощью таких вещей, как бинарный поиск по упорядоченной таблице занимает время O (log n), тогда как поиск по неупорядоченной таблице занимает O (N) время. Адриан Мейя: Большая таблица O и примеры
Запись Big O (и определение сложности времени) о темпах роста. Некоторые алгоритмы, которые принимают 2n , n и n / 2 , все растут с линейной скоростью и выражаются O(n). Таким образом, мы отбрасываем константу, предшествующую 'n', когда используем нотацию Big O, и допускаем, что она действительно полезна только для сравнения алгоритмов, которые принимают O(1), O(log n), O(n), O(n^2) и других показателей. StackOverflow: почему константа всегда отбрасывается из анализа больших О?
Лучшая причина, которую я нашел для этого, заключается в том, что эти константы зависят от реализации . Если мой компьютер WindowsXP 2002 года и ваш Windows10 компьютер 2019 года выполняют ту же задачу, WindowsXP 2n может занять время, которое ваш компьютер делает в n / 2 времени.
Часть недавно проведенных оптимизаций заключается в следующем: в моем программном обеспечении есть алгоритм, который проходит через список, скажем, 100 000 точек данных, чтобы получить максимальные и минимальные значения. Я использовал итерацию по всему списку, чтобы найти максимум, а затем итерации по всему списку, чтобы найти минимум, в двух разных функциях, которые были на расстоянии нескольких миль. Теперь я перебираю его один раз, чтобы найти максимальное и минимальное значения, а затем передаю два значения, пока они мне не понадобятся. Если мы предполагаем, что итерация по списку выполняется за n раз, тогда я использовал 2n время для итерации по списку дважды, вместо того, чтобы делать это во время n для итерации через список один раз. Неважно, какое оборудование вы используете, 18-летний компьютер или новый. Новый алгоритм выполняется в два раза быстрее.
int minValue = int.MaxValue;
int maxValue = int.MinValue;
foreach(int entry in myList)
{
if (entry < minValue) minValue = entry;
if (entry > maxValue) maxValue = entry;
}
(Если вы заметили, что это C# /. NET и, скажем, используйте LINQ вместо этого, чтобы ускорить алгоритм, вы явно упустили суть вопроса)
Мне не удалось найти краткий, понятный способ сказать это, как обозначение Big O. Большая О, Большая Омега, Большая Тета, маленькая нотация - все связано со сложностью времени. Таким образом, все имеют дело только с темпами роста и опускают любую константу от n.
Один из способов, о котором я подумал, состоял в том, чтобы сравнить мои две реализации алгоритма и сказать, что для 10000 точек на производственном компьютере Windows10 алгоритм A занял 15 секунд, а алгоритм B - 7,5 секунд. Но мне не нужны временные метки, просто алгоритм B работает в два раза быстрее.
Я мог бы также отказаться от записи Big O и просто сказать, что алгоритм B требует одну итерацию через данные, чтобы выполнить ту же работу, что и алгоритм A, что требует двух итераций. Это работает, но не использует понятную терминологию. Я думаю, что хорошо понятная терминология будет полезна в официальных документах, где вы пытаетесь заявить, что ваш алгоритм работает за 1/100 времени другого алгоритма. Эта потребность в терминологии заключается в том, почему, я полагаю, люди в первую очередь придумали нотацию Big O!
Итак, есть ли четко определенная терминология? Или этот вопрос глуп, и любой, кто задается вопросом, должен просто продолжить свою жизнь?