2

晚上好，我想知道是否有人可以为我提供一个确定性算法的简单伪代码示例......我将不胜感激，一定会给你加分！！。谢谢

4

5 回答 5

5

对我来说，“确定性”可能意味着很多事情：

  • 给定相同的输入，每次都产生相同的输出。
  • 给定相同的输入，每次运行都需要相同的时间/内存/资源。
  • P可以通过确定性计算机在多项式时间内解决的复杂性类问题，而不是只能NP使用非确定性计算机在多项式时间内解决的复杂性类问题。

你是指这些中的哪一个？

最简单的确定性算法就是这个随机数生成器。

def random():
    return 4 #chosen by fair dice roll, guaranteed to be random

它每次都给出相同的输出，展示已知的O(1)时间和资源使用情况，并在PTIME任何计算机上执行。

于 2012-04-17T13:37:59.137 回答
1

你真的是说 DETERMINISTIC 而不是 NONdeterministic，我的意思是你在任何教程/指南/入门书中看到的几乎所有东西都是确定性的，例如

for i from 1 to 9 
    print i

将始终打印 123456789

于 2012-04-17T12:55:46.900 回答
0

这是检查给定数字是否为奇数的确定性算法的伪代码：

function is_odd(n):
    if n mod 2 = 1
    then return true
    else return false
于 2012-04-17T12:57:09.640 回答
0

确定性算法是一种算法，用非正式的术语来说，其行为是可预测的。给定一个特定的输入，它总是会产生相同的输出

public struct Point {
   public int x;
   public int y; 

   //other methods

   public override int GetHashCode() {
      return x ^ y;
   }
}

Point P=new Point();
p.x=6;
p.y=3;
int res= p.GetHashCode();
于 2012-04-17T13:03:08.300 回答
0

确定性算法只是具有预定义输出的算法。例如，如果您正在对严格排序的元素（不相等元素）进行排序，则输出定义明确，因此算法是确定性的。

事实上，大多数计算机算法都是确定性的。当您有一些并行化或一些仅根据某些非完整标准相等的元素时，通常会出现不确定性。

于 2012-04-17T12:55:39.473 回答