小编Or1*_*10n的帖子

作为递归深度,在QuickSort达到基本情况之前连续递归调用的最大数量,并注意到它(递归深度)是随机变量,因为它取决于所选择的枢轴.

我想要的是估计QuickSort的最小可能和最大可能的递归深度.

以下过程描述了QuickSort正常实现的方式:

QUICKSORT(A,p,r)
    if p<r
        q ? PARTITION(A,p,r)
        QUICKSORT(A,p,q?1)
        QUICKSORT(A,q+1,r)
    return A

PARTITION(A,p,r)
    x?A[r]
    i?p?1
    for j ?p to r?1
        if A[j] ? x
            i ? i +1
            exchange A[i] ? A[j]
    exchange A[i +1] ? A[r]
    return i +1

QuickSort中的第二次递归调用并不是必需的; 通过使用迭代控制结构可以避免它.这种技术也称为尾递归,它可以实现如下:

QUICKSORT_tail(A,p,r)
    while p<r
        q ? PARTITION(A,p,r)
        QUICKSORT(A,p,q?1)
        p ? q+1
    return A

在此版本中,最近一次呼叫的信息位于堆栈顶部,初始呼叫的信息位于底部.调用过程时,其信息被压入堆栈; 当它终止时,会弹出其信息.由于我假设数组参数由指针表示,因此堆栈上每个过程调用的信息都需要O(1)堆栈空​​间.我也相信这个版本的最大可能堆栈空间应该是θ(n).

所以,在所有这些之后,我如何估计每个QuickSort版本的最小可能和最大可能的递归深度？我在上述推论中是对的吗？

提前致谢.

我正在使用 Plotly 库来创建我的数据图表。我遇到的问题是，当我尝试在不同的选项卡中将它们分开时，它不会像预期的那样调整大小（仅使用高度，宽度可以），除了第一个选项卡的图表，它工作正常。

在我的 index.html 中，我有以下结构：

<script type="text/javascript" src="{{STATIC_URL}}myindex.js"></script>

<ul class="nav nav-tabs">
  <li class="active"><a data-toggle="tab" href="#var1">Var 1</a></li>
  <li><a data-toggle="tab" href="#var2">Var 2</a></li>
</ul>

<div class="tab-content">
  <div id="var1" class="tab-pane fade in active">

    <div class="thumbnail parent_container" style="margin-top: 100px;">
      <div class="thumbnail text-center chart">
          <div id="chart1">
          </div>
      </div>
      ...
    </div>

  </div>

  <div id="var2" class="tab-pane fade">

    <div class="thumbnail parent_container" style="margin-top: 100px;">
      <div class="thumbnail text-center chart">
          <div id="chart2">
          </div>
      </div>
      ...
    </div>

  </div>
</div>

必须创建图表的 myindex.js 部分如下所示：

$( document ).ready(function()
{
  "use strict";  

  var WIDTH_IN_PERCENT_OF_PARENT = 96; …