Разница между детерминированными и недетерминированными алгоритмами

В детерминированном алгоритме для данного конкретного входа компьютер всегда будет производить один и тот же результат, проходя через одни и те же состояния, но в случае недетерминированного алгоритма для одного и того же входа компилятор может выдавать разные выходные данные в разных прогонах. Фактически, недетерминированные алгоритмы не могут решить проблему за полиномиальное время и не могут определить, каков следующий шаг. Недетерминированные алгоритмы могут демонстрировать различное поведение для одного и того же ввода при разном выполнении, и в этом есть некоторая степень случайности.

Для реализации недетерминированного алгоритма у нас есть несколько языков, таких как Prolog, но в них нет стандартных операторов языка программирования, и эти операторы не являются частью каких-либо стандартных языков программирования.

Некоторые термины, относящиеся к недетерминированному алгоритму, определены ниже :

• choice (X): случайным образом выбирает любое значение из множества X.
• failure (): обозначает неудачное решение.
• success (): решение успешно, и текущий поток завершается.

Пример :

Problem Statement : Search an element x on A[1:n] where n>=1, on successful search return j if a[j] is equals to x otherwise return 0.

Non-deterministic Algorithm for this problem :

1.j= choice(a, n)
2.if(A[j]==x) then
    {
       write(j);
       success();
    }
3.write(0); failure();

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.