随机化算法的重要性
简介:
- Randomization is an important concept, so randomization algorithm is used in many fields, such as number theory computational geometry graph theory and distributed computing.
- The input of randomization algorithm is similar to that of deterministic algorithm, and there are a series of random bits that can be used by the algorithm for random selection.
- In other words, randomization algorithm is an algorithm whose behavior depends on input. Similar to deterministic algorithm, random selection is made as part of its logic.
- As a result, even for the same input, the algorithm gives different outputs.
- In other words, the algorithm is random; Therefore, its running time is usually explained by random variables.
优势:
- Randomization algorithm is known for its simplicity.
- Any deterministic algorithm can be easily transformed into a randomized algorithm. These algorithms are easy to understand and implement.
- The randomization algorithm is very efficient.
- Compared with any deterministic algorithm, they hardly occupy the execution time and space.
- Compared with deterministic algorithm, randomization algorithm shows better asymptotic bounds.
- In other words, the algorithm complexity of randomization algorithm is better than most deterministic algorithms.
- Reliability is an important problem in many key applications, because not all randomization algorithms can give correct answers.
- In addition, many randomization algorithms may not be terminated.
- Therefore, reliability is an important issue to be dealt with.
- The quality of randomization algorithm depends on the quality of random number generator as a part of the algorithm.
- Unlike other design paradigms, randomization algorithm does not use a single design principle.
- On the contrary, people should regard randomization algorithm as an algorithm designed using a set of principles.
- On the contrary, people should regard randomization algorithm as an algorithm designed using a set of principles.
以下小节列出了一些设计原则:
证人概念 :
- 这个原则涉及检查给定输入是否具有属性 X 的问题。
- 它是通过找到一个被称为证人或证书的特定对象来建立的。
- 证人被识别以证明输入确实具有期望的属性 x 的事实。
- 通过进行更少的试验，可以发现财产是否真的存在。
- 证人的在场是基于证人不在场的 X 财产的有力证明。这个原理用素性检验的例子来说明。
指纹 :
- By definition, fingerprints are short information representing larger objects.
- Fingerprint identification is a technology to compare two large objects only by comparing their short fingerprints.
- If the two fingerprints don't match, then objects A and B are different.
- However, if the fingerprints match, there is strong circumstantial evidence that the two objects are the same.
检查恒等式 :
- Let's assume that an algebraic expression is given. The problem is to check whether the evaluation result of the expression is zero.
- The principle of checking the identity is to plug the random variables of a given algebraic equation and check whether the evaluation result of the expression is zero.
- If it is not zero, then the given expression is not an identity.
- Otherwise, there is strong circumstantial evidence that the expression is identical with zero.
【随机采样和排序】 :
- The performance of the algorithm is sometimes improved by randomizing the input distribution or order.
- It can be observed that for some sort of input, the performance of the algorithm can be higher or just acceptable.
- Here, randomization leads to randomized ordering, division and sampling.
- In addition, the randomization algorithm uses random samples to collect information about the input distribution. The recruitment problem illustrates this point.
挫败对手 :
- Randomization algorithm can be regarded as a game between a person and an opponent, that is, a game between the person who proposed the algorithm and the opponent who tried to defeat the algorithm by designing appropriate input, which made the algorithm take longer.
- In other words, the randomization algorithm can be regarded as choosing an algorithm from a large group of deterministic algorithms, and this choice can be regarded as a scene where things become more difficult by giving random input, thus making tasks more difficult.
版权属于：月萌API www.moonapi.com，转载请注明出处
