了解随机算法的预期运行时间 -- algorithms 领域 和 time-complexity 领域 和 probability-theory 领域 和 randomized-algorithms 领域 和 average-case 领域 cs 相关 的问题

Understanding Expected Running Time of Randomized Algorithms


简体版||繁體版
3
vote

问题

中文

我想了解预期的运行时间和更糟糕的情况预期运行时间。

当我看到这个数字(源),

src =

$ i $是输入,$ s $是随机数的序列。

我不明白的是,从上面的等式中是指一个特定输入$ i $ x

给出预期运行时间的原因

我一直认为是为了一个问题$ pi $,$ e( pi)= sum_ {输入在输入}(pr(输入)* t(输入))$,不是正确的吗?< / p>

所以,假设Pr(x)是统一分布,我们要使用线性搜索找到以$ n $元素数组中搜索元素的问题的预期运行时间。

不是线性搜索的预期运行时间

$$ e(linearsearch)= frac {1} {n} sum_1 ^ ni $$

以及最糟糕的案例预期运行时间,不是具有最坏行为的时间复杂性吗?喜欢下图,

输入图像描述

如果有人可以帮助我理解上图的两个数字,我会非常感激。

提前谢谢。

英文原文

I want to understand the expected running time and the worse-case expected running time.

I got confused when I saw this figure (source),

source

where $I$ is the input and $S$ is the sequence of random numbers.

What I don't understand from the above equation is why the expected running time is given for one particular input $I$?

I always thought that for a problem $\pi$, $E(\pi) = \sum_{input \in Inputs}(Pr(input)*T(input))$ , isn't this correct?

So, let's assume Pr(x) is the uniform distribution, and we are to find the expected running time of the problem of searching an element in a $n$ element array using linear search.

Isn't the expected running time for linear search,

$$E(LinearSearch) = \frac{1}{n}\sum_1^ni $$

And what about the worst case expected running time, isn't it the time complexity of having the worst behavior? Like the figure below,

enter image description here

I would highly appreciate if someone can help me understand the two figures above.

Thank you in advance.

              

回答列表

7
 
vote
vote
最佳答案
 

这里有两个预期的运行时间概念。给定随机算法,其运行时间取决于随机硬币折叠。 预期的运行时间是对硬币抛出的运行时间的期望。此数量取决于输入。例如,随机枢轴的Quicksort具有预期的运行时间 $ theta(n log n)$ 。此数量取决于输入 $ n $

给定随机或确定性算法,也可以从某种固定分发中随机输入上的预期运行时间。例如,确定性 quicksort (用固定的枢轴)有预期的运行时间 $ theta(n log n)$ 在随机分布的长度输入中 $ n $ 。这被称为平均病例分析。您的线性搜索示例适合此类别。

相关概念是平滑分析,其中我们对特定输入的邻域中的算法的预期运行时间感兴趣。例如,虽然 simplex算法在某些输入上具有指数运行时间,在"附近" 每个输入它在预期中的多项式时间中运行。

 

There are two notions of expected running time here. Given a randomized algorithm, its running time depends on the random coin tosses. The expected running time is the expectation of the running time with respect to the coin tosses. This quantity depends on the input. For example, quicksort with a random pivot has expected running time $\Theta(n\log n)$. This quantity depends on the length of the input $n$.

Given either a randomized or a deterministic algorithm, one can also talk about its expected running time on a random input from some fixed distribution. For example, deterministic quicksort (with a fixed pivot) has expected running time $\Theta(n\log n)$ on a randomly distributed input of length $n$. This is known as average-case analysis. Your example of linear search fits this category.

A related concept is smoothed analysis, in which we are interested in the expected running time of an algorithm in the neighborhood of a particular input. For example, while the simplex algorithm has exponential running time on some inputs, in the "vicinity" of each input it runs in polynomial time in expectation.

 
 

相关问题

0  搜索数组的平均时间复杂性[关闭]  ( Average time complexity of searching an array ) 
关闭。这个问题需要详细信息或清晰度。它目前不接受答案。 想要改进这个问题?添加详细信息并阐明编辑此帖的问题。 关闭 6年前。 ...

6  这种可恶劣算法的时间复杂程度是多少?  ( What is the time complexity of this atrocious algorithm ) 
这一探讨了故意糟糕的算法;信用到 benneh 在XKCD论坛上的伪代理算法,我'转换为python,所以你可以实际运行它: def sort(list): if len(list) < 2: return list else: if list[0] <= mini...

2  查找可快速包含特定元素的$ k $子集  ( Find k subsets containing a particular element quickly ) 
假设$ U $的$ N $子集。我想快速(在平均案例方面)找到包含$ e in u $的k $(&lt; n)$(呼叫这个提取(e))。元素是整数。 到此效果,我想预处理/编码$ N $子集,以便这种提取操作可​​能相对快速地发生,而不管y $ is(假设此项目均匀地选择查询)。 我没有良好的直觉,以便各种方法做到...

2  循环的时间复杂性  ( Time complexity of this while loop ) 
所以,我想知道以下代码的时间复杂性: x = (float) rand() / rand(); // T(4) while (x >= 0.01) // T(?) { x *= 0.8; // T(?) x T(2) } 假设所有基本操作都是完善的一次,是最好的情况t(1) - 恒定的时...

2  如何完成工作的平均案例运行时间(和其他算法)?  ( How to go about working the average case run time of this trivial algorithm and ) 
这是一个类似的算法到一个我在上一个问题中使用的算法,但我试图在这里说明一个不同的问题。 for (int i = 0; i < numbers.length - 1; i++) { for (int j = i + 1; j < numbers.length; j++) { if (num...

0  将项目附加到数组的平均运行时间是多少?  ( What is the average runtime of appending items to arrays ) 
是一年中的一年中的时间在最终考试中,我正在准备现在我的准备,我在理解将物品附加到阵列的运行时间来看,我在热水中找到自己。 基本上,我知道有不同的方式将物品附加到数组,但请考虑此方法附加方法和它的平均运行时。我已经设法找到了另一个运行时间,但不是它的平均值。 此方法在课堂上将项目介绍给我,并且诀窍是在满满的时候加倍数组...

3  为什么线性搜索平均是$ frac {n} {2} $比较?  ( Why does linear search have fracn2 comparisons on average ) 
我正在阅读线性搜索上的wikipedia页面,提到平均$ frac {n} {2} $比较。 我自己尝试一下自己工作。 首先我被认为是案件的数量。当目标值为1美元的$ 1,$ 2 $ nd,...,$ n $ th列表时,有$ N $案例。还有一个条目根本不在列表中的情况,所以我们有$ n + 1 $案例。 接下来...

14  泡沫排序中的掉次数  ( Expected number of swaps in bubble sort ) 
给定数组$ $ n $整数,数组中的每个元素都可以通过一些概率$ p [i] $,$ 0 leq i&lt; n $。我必须找到将使用泡泡排序对阵列进行排序。 我已经尝试了以下内容: 元素$ a [i]&gt的概率; a [j] $ i&lt;可以从给定的概率轻松计算J $。 使用上面的,我已经计算了次数的...

1  系列的渐近生长  ( Asymptotic growth of a series ) 
我们如何证明: $$ sum_ {k = 1} ^ {c log n-1} :k cdot left( frac {1} {2} 右)^ { frac {k} {3}} 在o o 左(1 右) quad mbox {?} $$ ...

5  证明二进制搜索的平均案例复杂性是O(log n)  ( Proving that the average case complexity of binary search is olog n ) 
我知道二进制搜索的平均和最坏情况复杂性是O(log n),我知道如何使用复制关系证明最坏的情况复杂性是O(log n)。 但是,我如何证明二进制搜索的平均案例复杂性是o(log n)? ...

15  Knuth,De Bruijn和Rice(1972)的“种植平面树的平均高度”  ( On the average height of planted plane trees by knuth de bruijn and rice 197 ) 
我正在尝试派生只有基本手段的标题(没有生成函数,没有复杂的分析,没有傅立叶分析,虽然具有更低的精度。简而言之,我希望证明具有$ N $节点的平均身高$ H_N $(即,从根到叶子的最大节点数)满足$ h_n sim sqrt { pi n} $。 轮廓如下。让$ a_ {nh} $是高度小于或等于$ h $的树的...

2  问题发现PESIN MAX算法的平均案例  ( Trouble finding average case of a find max algorithm ) 
我正在尝试找到最大的平均速度由下面包含的算法查找。 findMax(list): maxNum = -oo # negative infinity for k = 0 to len(list)-1: if list[k] > maxNum: maxNum=...

3  在通用布尔公式中找到真实或错误分配的硬度?  ( Hardness of finding a true or a false assignment into a generic boolean formula ) 
我读过一些研究,分析了平均案例中SAT解决的硬度。 实际上,对于3CNF公式,如果将子句与变量的比率计算为变量的比率,则存在求解公式的间隔(或多或少为4和5)。但它很容易(在0到4之间)比率5的满足分配的高概率和不可挑离的分配的高可能性。 我的问题是,概述了不正常形式的通用公式。我们可以对其硬度说些什么? ...

3  预期成本和算法平均成本之间有什么区别?  ( What is the difference between expected cost and average cost of an algorithm ) 
在经历概率/平均分析算法时,我发现在平均成本和预期成本的某个地方写入。有人可以告诉我完全预期的成本代价是什么。我认为我们照顾了活动的可能性,同时找到与平均成本不同的预期成本。 ...

11  评估给定的Bubblesort算法的平均时间复杂度。  ( Evaluating the average time complexity of a given bubblesort algorithm ) 
考虑到Bubblesort的伪代码: FOR i := 0 TO arraylength(list) STEP 1 switched := false FOR j := 0 TO arraylength(list)-(i+1) STEP 1 IF list[j] > list[...

1  一种简单的最大发现算法的平均分析  ( Average case analysis of a simple max finding algorithm ) 
给出了这段代码: Valid combinations: 1 2 (1 - 2 connection) 2 3 (2 - 3 connection) 3 1 (3 - 1 connection) 1 2, 2 3 (1 - 3 connection) 1 2, 3 1 (2 - 3 connect...

0  找到最大算法的平均时间复杂度  ( Finding the average time complexity for a max algorithm ) 
我试图找到最大值的平均例外情况在下面的算法 99887665544330 。 find_max(L): max = -oo # negative infinity for k = 0 to len(L)-1: if L[k] > max: ma...

7  在流中保持k $最小的整数的复杂性  ( Complexity of keeping track of k smallest integers in a stream ) 
我需要分析在线算法的时间复杂性,以跟踪从$ $ numb的流中追踪最低$ k $号码。该算法是 假设流中的$ i $ th号码是$ s_i $。 保持尺寸的最大堆$ k $。 如果堆包含少于$ k $元素,请为堆添加$ s_i $。 否则:如果$ s_i $小于堆中的最大元素(即堆的根),请用$ s_i $替换堆的...

4  用于执行插入的单个链接列表的平均时间复杂性是多少?  ( What is the average time complexity for a single linked list for performing an ) 
我认为这将是一个非常简单的 O(n) B.C.您可以在列表中使用任何内插入。 列表越长,平​​均越长,才能完成插入。 但是,根据 bigocheatsheet 它是 O(1) 或没有依赖于大小列表。 这里有什么问题? ...

1  您如何表达关于不成功搜索的定理声明平均 - 与量子散列中的不成功搜索?  ( How do you express the theorem statement about unsuccessful search on average ca ) 
我正在阅读CLRS和定理11.1它状态: 在其中通过链接解析冲突的哈希表中,在简单统一散列。 我试图了解如何用量词表达这个定理($ 存在, forall $)以及它如何与"平均案例" 时间(精确,它们的平均案例时间)。 是定理是所有或任何关键的声明?或者它是平均所有关键的关键,并且"平均" 是什么意思,严格呢? ...

1  鉴于算法,其运行时案例的概率是什么?  ( Given an algorithm what are the probabilities for its run time cases ) 
我被赋予此算法 ,我也给出了$ 1 leq k leq n $。 如果我们让x是执行第2行的次数,那么我应该找到不同案例的运行时概率。 因此我知道最好的情况是[n-1] = k $,因为第2行只会被调用一次。 我知道$ k 1,2,...... n $。 和施工$ a [n-1] 在0,1,2,... n...

2  平均案例分析帮助  ( Average case analysis help ) 
我暂时试图了解如何解决以下问题。有人可以请向初学者解释平均病例分析吗? 考虑以下算法a,它用作输入比特串b = b_1,b_2,...,b_n(每个b_i为0或1),并执行以下操作: A(b,n) k = 0 FOR i = 1 TO n DO IF b_i = 1 THEN k = k ...

4  输入数据概率生成模型下NP-Hard优化问题的近似值或解的概率硬度  ( Probabilistic hardness of approximation or solution of np hard optimization prob ) 
如此,在生物学(DNA序列)中,序列对准是最长常见的通用,其中两个序列的对准通常具有线性函数,每个序列将有多少空间和每个可能的一对对齐字符显示在对齐中。就像最长的常见子序列一样,在使用动态编程的二次时间中,在任意线性评分方案下找到两个字符串的最佳对准。 (Constleman-Wunsch算法)。使用线性评分方案和询...

6  二进制搜索树和AVL树的平均深度  ( Average depth of a binary search tree and avl tree ) 
我的教授最近提到二进制搜索树中的节点的平均深度将是$ o(log(n))$ why $ n $是树中的节点量。我最终绘制了一堆二进制搜索树,我不认为我是正确了解这个概念。例如,如果$ n = 4 $ the tree,则将具有最大3美元或节点的最大深度的节点,最大深度为2美元。在最大值为3美元的情况下,我们将有0美元...

0  Quicksort的平均案例运行时间分析很好参考  ( Good reference for average case runtime analysis of quicksort ) 
我是编程中的初级知识,知识技术知识。我被分配到Quicksort的平均案例分析中进行"阅读项目" 。我的意思是我必须在课堂上呈现它。现在,我需要一个很好的来源,我可以阅读它并找到我可以在演示中包含的材料。至于我对算法的现有知识,人们可以假设我几乎不知道,除了"只是代码" ,什么都没有任何关于他们的分析。任何具有严格证...

相关问题

0  搜索数组的平均时间复杂性[关闭] 
6  这种可恶劣算法的时间复杂程度是多少? 
2  查找可快速包含特定元素的$ k $子集 
2  循环的时间复杂性 
2  如何完成工作的平均案例运行时间(和其他算法)? 
0  将项目附加到数组的平均运行时间是多少? 
3  为什么线性搜索平均是$ frac {n} {2} $比较? 
14  泡沫排序中的掉次数 
1  系列的渐近生长 
5  证明二进制搜索的平均案例复杂性是O(log n) 
15  Knuth,De Bruijn和Rice(1972)的“种植平面树的平均高度” 
2  问题发现PESIN MAX算法的平均案例 
3  在通用布尔公式中找到真实或错误分配的硬度? 
3  预期成本和算法平均成本之间有什么区别? 
11  评估给定的Bubblesort算法的平均时间复杂度。 
1  一种简单的最大发现算法的平均分析 
0  找到最大算法的平均时间复杂度 
7  在流中保持k $最小的整数的复杂性 
4  用于执行插入的单个链接列表的平均时间复杂性是多少? 
1  您如何表达关于不成功搜索的定理声明平均 - 与量子散列中的不成功搜索? 
1  鉴于算法,其运行时案例的概率是什么? 
2  平均案例分析帮助 
4  输入数据概率生成模型下NP-Hard优化问题的近似值或解的概率硬度 
6  二进制搜索树和AVL树的平均深度 
0  Quicksort的平均案例运行时间分析很好参考 



© 2021 it.wenda123.org All Rights Reserved. 问答之家 版权所有