依靠硬币翻转的while循环的预期运行时间是多少？

问题描述

我一直在为我的CS2类开发Java的SkipList实现，在分析了所有方法的运行时（出于乐趣）之后，我在确定以下各项的平均运行时遇到了问题：

// Returns 1 with 50% probability, 2 with 25% probability,
// 3 with 12.5% probability, and so on, without exceeding maxHeight
private static int generateRandomHeight(int maxHeight)
{
    int height = 1;
    // At most O(maxHeight) which is O(log(n))
    // Best case is O(1) and on average O(log(log(n)))??
    while (--maxHeight > 0 && Math.random() 

我知道最佳运行时间为O（1），最差运行时间为O（h），由于h = = log2（n）⌉（ n）的对数以2为底

问题是，该功能的平均预期运行时间是多少？>]

乍看之下，我假设它应该是O（log（log（n（n））））。我将这个问题带给了我的TA，在与他们讨论之后，我们依靠的是O（1）的平均运行时间，因为我们很可能只进行一次迭代或根本不进行迭代（例如50％）。

我一直在为我的CS2类研究Java的SkipList实现，在分析了所有方法的运行时（出于娱乐目的之后，我在确定以下各项的平均运行时遇到了问题：...

] >

public static void main(String[] args) {
    List l = new ArrayList();

    for(int n = 0; n  l) {
    double sum = 0;

    for(int i : l) {
        sum += i;
    }

    return sum / l.size();
}

1.011
0.986
1.046
0.991
0.953
0.984
1.017
0.973

思路：

[具有复杂度时，计算复杂度通常很复杂。但是您是对的，它是O（1），但不完全是O（1）。 O（1）定义为常量，这意味着无论您输入什么，运行时间都将相同。但是，就您而言，Math.random()是不可预测的。但是，尽管如此，它仍然为O（1），因为随着n的增加，运行时间保持相对恒定。我进行了一次测试，以查看循环迭代的次数，并且我的结果确实相似。

public static void main(String[] args) {
    List l = new ArrayList();

    for(int n = 0; n  l) {
    double sum = 0;

    for(int i : l) {
        sum += i;
    }

    return sum / l.size();
}

 以上内容就是爱站技术频道小编为大家分享的依靠硬币翻转的while循环的预期运行时间是多少？看完以上分享之后，大家应该都知道这个运行时间是多少了吧。