@val18

Как определять сложность алгоритма?

Как правильно высчитывать сложность алгоритма? Какая сложность алгоритма в О нотации будет для сложения/умножения матриц? Есть ли какая-то формула или методика для рассчёта?!
  • Вопрос задан
  • 1480 просмотров
Пригласить эксперта
Ответы на вопрос 3
@Zolg
Какая сложность алгоритма в О нотации будет для сложения/умножения матриц?

Умножение матриц - не алгоритм, а операция.
Алгоритм конкретный способ ее реализации.
Сложность 'наивного' алгоритма умножения - O(n^3)
Сложность, например, алгоритма Штрассена O(n^2,81)

Есть ли какая-то формула или методика для рассчёта?!
элементарно: считаете количество (для О-нотации - максимальное) элементарных операций, необходимых для вычисления алгоритма для входных данных размерности n. Константу сокращаете.

ps:
'вычислительная сложность' показывает только отношение того, насколько дольше будет вычисляться алгоритм, при увеличении размера входных данных. но совершенно ничего не говорит о объеме вычислений в абсолютных цифрах.
многие 'быстрые' алгоритмы на малых размерах входных данных (в абсолютных цифрах) проигрывают 'медленным': да, количество вычислений с ростом n растет медленней, но вплоть до какого-то n самих вычислений больше
Ответ написан
Комментировать
BasiC2k
@BasiC2k
.NET developer (open to job offers)
Сложность можно переложить в человеко-часы на реализацию.
Например:
- я реализовал алгоритм за 10 часов. Это было сложно.
- а я реализовал этот же алгоритм за 2 часа. Это было не сложно.

Само по себе понятие "сложность" - субъективное и зависит от множества факторов:
- опыт реализации подобных задач;
- наличие специфических знаний;
- среда разработки;
- самочуствие и тд.
Ответ написан
@Mercury13
Программист на «си с крестами» и не только
Начнём с того, что такое символы Ландау (не того, немца Эдмунда Ландау) O(f(n)) и o(f(n)) при n→∞.
g(n) = O(f(n)), если при достаточном n g(n)≤cf(n).
g(n) = O(f(n)), если g(n)/f(n) → 0 при стремлении n→∞.
Таким образом…
• Символы Ландау отражают изменение чего-то (времени, памяти и т.д.) при n→∞.
• Если, например, два цикла друг в друге и каждый по n — пишем O(n²). Например, для умножения матриц n×n:
для i = 1…n
  для j = 1…n
    s = 0
    для k = 1…n
      s += a[i,k]·b[k,j]
    c[i,j] = s

Тут три вложенных друг вы друга цикла по n — так что сразу же пишем O(n³).
• Если g(n) = O(n), то g(n) = O(n²), потому мы не грешим против истины. Но если вдруг оказалось, что внутренний цикл — это извлечение из очереди и через эту самую очередь пройдут, например, 2n событий — внешний цикл выполняется O(n) раз и внутренний O(n) раз; оценка алгоритма сразу же превращается в O(n).
• Константы мы, разумеется, выкидываем: и 2n², и 200n² = O(n²). Также выкидываем те части, чей порядок меньше, чем самый крупный: n²+n log n = O(n²). Кстати, потому мы и не пишем основание логарифма: логарифмы разных оснований отличаются множителем.
• Но иногда константы важны. Скоростные методы умножения матриц имеют насколько большую константу при n2,81, что реально они начинают иметь смысл где-то со 100×100 (а то и крупнее). По той же причине живёт двоичный алгоритм поиска подстроки — он имеет крайне низкую константу при n² и ещё парочку полезных свойств.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы