Какое ожидаемое время выполнения l oop зависит от подбрасывания монеты? - PullRequest
Новая
       74

Какое ожидаемое время выполнения l oop зависит от подбрасывания монеты?

0 голосов
/ 25 февраля 2020

Я работал над реализацией SkipList в Java для моего класса CS2, и после анализа времени выполнения всех моих методов (для забавы) у меня возникла проблема с определением среднего времени выполнения следующего: 

// 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() < .5)
            height++;

    return height;
}

Я знаю, что наилучшим временем выполнения является O (1), а худшим - O (h), которое гарантированно будет O (log (n)), поскольку h = ⌈log₂ (n) ⌉ (потолок лог-базы два из n) .

Вопрос в том, каково среднее ожидаемое время выполнения этой функции ?

На первый взгляд, Я предположил, что ожидается O (log (log (n))). Я задал этот вопрос своим TA, и после обсуждения с ними мы полагаемся на среднее время выполнения O (1), так как наиболее вероятно, что мы повторяем только один раз или не делаем вообще (например, 50%).

1 Ответ

2 голосов
/ 25 февраля 2020

Расчет сложности часто бывает сложным, когда у вас есть вероятность. Но вы были правы, это был O (1), но не совсем O (1). O (1) определяется как константа, что означает, что независимо от того, что вы вводите, время выполнения будет одинаковым. Однако в вашем случае Math.random() не предсказуемо. Но, тем не менее, это все равно O (1), потому что время выполнения остается относительно постоянным при увеличении n. Я сделал тест, чтобы увидеть, сколько раз l oop повторяется, и мои результаты были действительно похожи. 

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

    for(int n = 0; n < 100; n ++) {
        for (int i = 0; i < 1000; i++) {
            for (int j = 0; j < n; j++) {
                if (Math.random() < 0.5) {
                    l.add(j);
                    break;
                }
            }
        }

        System.out.println(average(l));
        l.clear();
    }


}

private static double average(List<Integer> l) {
    double sum = 0;

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

    return sum / l.size();
}

Вот несколько результатов. Как видите, они колеблются около 1. 

1.011
0.986
1.046
0.991
0.953
0.984
1.017
0.973
...