我对算法的完整性和完整性感到困惑.
声音算法永远不会返回错误结果.该算法有可能不返回任何内容吗？
完整的算法将解决所有输入.算法返回的结果会影响算法的完整性.例如,如果排序算法将获取所有输入并返回一个列表,但它不保证返回一个排序列表,它只是一个不健全的算法,但它是否完整？
Eri*_*c Z 16
让S成为一组正确的答案.
一个完善的算法从未包括一个错误的答案S,但它可能会错过一些正确的答案.=>不一定"完整".
一个完整的算法应该得到每个正确的答案S:包括完整的正确答案集.但它可能包括一些错误的答案.它可能会为单个输入返回错误的答案.=>不一定是"声音".
所以,
声音算法永远不会返回错误结果.该算法有可能不返回任何内容吗？
一定是对的.但它什么都不会返回.(错过了部分)
例如,如果排序算法将获取所有输入并返回一个列表,但它不保证返回一个排序列表,它只是一个不健全的算法,但它是否完整？
这得看情况.
如果算法返回的列表形成了集合S,那么它就完整了,因为包含了每个正确的答案.它并不一定意味着每一个输出都是正确的.例如S = {b1, b2}.假设,对于输入a1,正确的输出是b1; 对于输入a2,正确的输出是b2.如果算法返回b2了a1,b1对a2,它是完整的,但不健全.
在另一方面,如果算法总是返回解决b1两个a1和a2,这显然不完整.
因此,您不能仅通过其健全性来推断算法是否完整,反之亦然.
请参阅7种的方式接近可靠性和完备性,同时在这里.
Ram*_*lat 10
这个比喻会让你理解这个概念.
有钓鱼比赛.目标是捕获重量超过1公斤的鱼.有两个竞争者,Sunada和Compila.每个人都用自己的湖泊钓鱼.每个湖泊都有完全相同数量的鱼类(100种鱼类),其中鱼类的鱼类数量完全相同,重量超过1公斤(50条鱼类).
裁判以哨子开始比赛.他们都捕到许多鱼,直到时间结束.现在它来计算符合规则的鱼类.裁判首先开始对Sunada捕获的所有鱼类进行加重.令人惊讶的是,所有被Sunada捕获的鱼体重超过1公斤!但他只捕获了45条鱼.
另一方面,Compila捕获了60条鱼.似乎Compila赢了,但裁判还没决定.因为可能少于45条鱼的重量超过1公斤.在统计和加权后,裁判称有50条符合规则的鱼类使Compila成为赢家.
现在在这个类比中,Sunada捕获的所有鱼都符合规则,这使他完美无瑕!另一方面,Compila捕获了符合规则的所有鱼类,这使得Compila完全完整!