一个接近最佳的随机算法,用于可探索的堆选择
Sander Borst1, Daniel Dadush1,2, Sophie Huiberts3
1Centrum Wiskunde & Informatica (CWI), Amsterdam, The Netherlands.
概括
本研究引入了一种新的随机算法,用于选择二进制堆中的第n最小值,提高搜索效率. 该算法实现了对无意识的对手近乎最佳的性能,推进了堆选择策略.
科学领域:
- 计算机科学 计算机科学
- 算法分析 算法分析
背景情况:
- 选择二进制堆中的第n最小值的问题,称为可探索堆的选择,对于优化像分支和绑定的算法中的搜索策略至关重要.
- 之前的研究已经建立了具有特定时间和空间复杂性的确定性和随机算法.
研究的目的:
- 开发一个更有效的随机算法,用于可探索的堆选择.
- 改进现有的随机运行时间,同时分析时空权衡.
主要方法:
- 一个新的随机算法被设计为可探索的堆选择.
- 分析了算法的性能与一个无意识的对手.
- 为在特定空间约束范围内运行的算法建立了一个下限.
主要成果:
- 新的随机算法实现了对一个无视的对手的运行时间为O (n ^ 2 / 3)).
- 这比以前的随机算法有了显著的改进.
- 一个Omega (n^{1/3)) 的下界被证明是使用O (n^{1/3)) 空间的算法.
结论:
- 开发的随机算法为可探索堆选择提供了近乎最佳的解决方案.
- 这些发现表明,这个问题的空间和时间复杂性之间存在有利的权衡.
- 这项研究促进了对数据结构中高效搜索策略的理解.
相关概念视频
Randomized Experiments
6.7K
The randomization process involves assigning study participants randomly to experimental or control groups based on their probability of being equally assigned. Randomization is meant to eliminate selection bias and balance known and unknown confounding factors so that the control group is similar to the treatment group as much as possible. A computer program and a random number generator can be used to assign participants to groups in a way that minimizes bias.
Simple randomization
Simple...
Simple randomization
Simple...
6.7K
Random Sampling Method
10.9K
Sampling is a technique to select a portion (or subset) of the larger population and study that portion (the sample) to gain information about the population. Data are the result of sampling from a population. The sampling method ensures that samples are drawn without bias and accurately represent the population. Because measuring the entire population in a study is not practical, researchers use samples to represent the population of interest. Among the various sampling methods used by...
10.9K
Group Design
8.9K
The most basic experimental design involves two groups: the experimental group and the control group. The two groups are designed to be the same except for one difference— experimental manipulation. The experimental group gets the experimental manipulation—that is, the treatment or variable being tested—and the control group does not. Since experimental manipulation is the only difference between the experimental and control groups, we can be sure that any differences between...
8.9K
Cluster Sampling Method
11.6K
Appropriate sampling methods ensure that samples are drawn without bias and accurately represent the population. Because measuring the entire population in a study is not practical, researchers use samples to represent the population of interest.
To choose a cluster sample, divide the population into clusters (groups) and then randomly select some of the clusters. All the members from these clusters are in the cluster sample. For example, if you randomly sample four departments from your...
To choose a cluster sample, divide the population into clusters (groups) and then randomly select some of the clusters. All the members from these clusters are in the cluster sample. For example, if you randomly sample four departments from your...
11.6K
Sampling Plans
163
Sampling is a crucial step in analytical chemistry, allowing researchers to collect representative data from a large population. Common sampling methods include random, judgmental, systematic, stratified, and cluster sampling.
Random sampling is a method where each member of the population has an equal chance of being selected for the sample. It involves selecting individuals randomly, often using random number generators or lottery-type methods. For example, when analyzing the properties of a...
Random sampling is a method where each member of the population has an equal chance of being selected for the sample. It involves selecting individuals randomly, often using random number generators or lottery-type methods. For example, when analyzing the properties of a...
163
Stratified Sampling Method
11.7K
Sampling is a technique to select a portion (or subset) of the larger population and study that portion (the sample) to gain information about the population. The sampling method ensures that samples are drawn without bias and accurately represent the population. Because measuring the entire population in a study is not practical, researchers use samples to represent the population of interest.
To choose a stratified sample, divide the population into groups called strata and then take a...
To choose a stratified sample, divide the population into groups called strata and then take a...
11.7K


