Если алгоритм имеет два подалгоритма, то в лучшем случае для подалгоритма A1 для данного входа это худший случай для подалгоритма A2. Как я могу найти общую сложность алгоритма? Просто я имею в виду Ω(N) + O(N)=? Я знаю, что если алгоритмы находятся в последовательном порядке выполнения, общая сложность составляет O (N) + O (N) и во вложенном порядке O (N) * O (N).
Подскажите пожалуйста в обоих случаях, когда в последовательном и во вложенном порядке
По существу Ω(N) + O(N)= Ω(N). Потому что O(N) означает более низкий (или самое большее тот же) порядок Ω(N). При их суммировании нижний порядок можно опустить.
SET + SET? Я не знаком со стандартным определением для него: |
- person amit; 23.09.2012
Если ваш алгоритм включает одну операцию, которая занимает, например, O(N) времени, а другую — O(N^2), то общая сложность равна O(N^2). Нет такой вещи, как O(N^2 + N). То же самое касается Ω(). Это отвечает на ваш вопрос о «порядке последовательного выполнения».
Если ваш алгоритм включает N операций, каждая из которых занимает O(N) времени, то общая сложность будет O(N^2). То же самое касается Ω(). Вы просто умножаете многочлены и берете член, который быстрее всего растет с увеличением N. Это отвечает на ваш вопрос о «вложенном порядке выполнения».
