1. Этот сайт использует файлы cookie. Продолжая пользоваться данным сайтом, Вы соглашаетесь на использование нами Ваших файлов cookie. Узнать больше.

Класс сложности алгоритма

Тема в разделе "Научные вопросы", создана пользователем Stephen, 23.05.06.

  1. Stephen

    Stephen Участник

    294
    0
    Вот вопрос. Есть некий алгоритм. Нужно доказать или или иным способом определить его класс сложности. Интересуют теоретический и экспериментальный подходы к определению.

    Очень нужна ссылка на букварь. Пробелы в образовании сильно мешают.
     
  2. Moonkan

    Moonkan Активный участник

    1.832
    0
    Речь идет о классах N , P , NP ?
    посмотри тут к примеру
    http://nature.web.ru/db/msg.html?mid=1157083&uri=node13.html
    Вообще мне кажется надо искать по словам типа автомат (машина) Тьюринга, формальные языки и т.д.
    Термины могут быть не точны так как изучаю это на немецком. Могу поскать литературу , может что на русском найду

    Теоретически речь видимо пойдет о решении проблемы с помошью машины Тьюринга и о анализи времени которое она на это затратит.

    Если же речь идет об анализе времени работы алгоритма , (к примеру одного из вариантов сортировки quicksort , heapsort ) то тут надо смотреть в зависимости от размера массива в трех случаях : лучший , средний и худший. Нас както учили выводить формулу для суммы выполнения всех строк и ее приближения с помощью "О-большого".

    http://www.ksu.ru/f9/bin_files/24.pdf посмотри еще тут вроде то что надо
     
    Последнее редактирование: 23.05.06
  3. AlTk

    AlTk Читатель

    10.699
    0
  4. Caps

    Caps Активный участник

    4.342
    18
    Если честно, то меня ничего из ссылок не впечатлило. Около, но не совсем то. Скажем так, я не нашел в них какого-либо вменяемого упоминания о задачах типа 3-сочетание (сколько их там базовых, 6 ?) .
    Ну и моя любимая тема "P=NP" не раскрыта. :)

    Надо все же попробовать найти книгу "Вычислительные машины и труднорешаемые задачи". Авторы, если не изменяет память Гэри и Джонсон. Тхе бест в этом вопросе.