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

## Understanding Expected Running Time of Randomized Algorithms

3

### 问题

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

$$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),

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,

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

## 回答列表

7

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  这种可恶劣算法的时间复杂程度是多少？  ( What is the time complexity of this atrocious algorithm )

2  查找可快速包含特定元素的$k$子集  ( Find k subsets containing a particular element quickly )

14  泡沫排序中的掉次数  ( Expected number of swaps in bubble sort )

1  系列的渐近生长  ( Asymptotic growth of a series )

5  证明二进制搜索的平均案例复杂性是O（log n）  ( Proving that the average case complexity of binary search is olog n )

15  Knuth，De Bruijn和Rice（1972）的“种植平面树的平均高度”  ( On the average height of planted plane trees by knuth de bruijn and rice 197 )

2  问题发现PESIN MAX算法的平均案例  ( Trouble finding average case of a find max algorithm )

3  在通用布尔公式中找到真实或错误分配的硬度？  ( Hardness of finding a true or a false assignment into a generic boolean formula )

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 )

1  一种简单的最大发现算法的平均分析  ( Average case analysis of a simple max finding algorithm )

0  找到最大算法的平均时间复杂度  ( Finding the average time complexity for a max algorithm )

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 )