"Спуск" правил

by Темных Сергей 10.08.2009 17:40:00

При формулировании сложности было зафиксировано, что сложность для зависимых  a и b растет как a * b;  но для статичной системы это еще не страшно - объем работы большой, но еще конечный.
А теперь представьте, что b часто меняется, и a - периодически тоже, да и само образование пар a и b - тоже меняется, и сложность как всегда сразу же зашкаливает.
 

Для системы в целом часто формулируются разнообразнейшие правила (ограничения, требования и т.д.) Сложность оценки этих правил огромна, особенно для динамической системы. Для борьбы с этим, исходное правило для системы в целом - стоит переформулировать в терминах локальной небольшой части.

Рассмотрим, для примера, правило - "алгоритм должен завершаться". Если решать задачу в лоб, то сложность получится = O(2^кол-во операторов изменяющих направления выполнения кода), но если помнить, что для независимых частей - сложность растет лишь линейно, а не экспонециально - то можно предложить более оптимальный путь. Можно применить методику "спуска" правила которая заключается в следующем: исходное правило переформулируется в терминах как можно меньших кусочкев системы,  плюс разбирается и фиксируется, когда при объединении этих кусочкев  - в рамках исходного правила - можно считать, что кусочки друг от друга не зависят, а когда - зависят.

Для рассматриваемого примера, если остановится на отдельный операторах, то можно заметить что:
1. простые операторы всегда заканчиваются
2. условные тоже всегда заканчиваются
3. операторы-циклы заканчиваются, если хоть когда-нибудь срабатывает условие выхода из цикла
4. goto-оператор невозможно локально оценить
также можно заметить, что если каждый кусочек останавливается, то объединение кусочкев тоже останавливается.

в итоге, можно сформировать простые правила, которые легко проверяются локально:
1. в программе не должно быть goto
2. цикл на каждой итерации должен "приближаться" к точке выхода из цикла. кол-во шагов по приближению - должно быть конечным.

и это нам позволило от оценки сложности- O(2^кол-во операторов изменяющих направления выполнения кода), перейти к оценке сложности - O(кол-во всех операторов, кроме операторов цикла) + O(кол-во for-ов)

Оценок нет

  • Currently 0/5 Stars.
  • 1
  • 2
  • 3
  • 4
  • 5

Tags:

Похожие записи

Powered by BlogEngine.NET 1.3.1.0
Theme by Mads Kristensen

Сергей Темных

Модулятор


Calendar

<<  Август 2017  >>
повтсрчепясуво
31123456
78910111213
14151617181920
21222324252627
28293031123
45678910

View posts in large calendar

Страницы

    Последние комментарии

    Категории

    None


    Disclaimer

    The opinions expressed herein are my own personal opinions and do not represent my employer's view in anyway.

    © Copyright 2017

    Sign in