Могут ли алгоритмы иметь одинаковую сложность времени в лучшем и худшем случаях? - PullRequest
0 голосов
/ 27 июня 2011

Возможно ли, чтобы алгоритм / программа имели одинаковое время наихудшего и наилучшего случая?

Например:

public static int factorial(int number)
{
    factorial = 1; 
    for (i = 1; i <= number; i++) 
        factorial = factorial * i;
}

Это программный сегмент для факториальной проблемы, и я пытался решить из-за сложности времени. Кажется, у него нет худшего и лучшего случая, так как какой бы ввод у вас ни был, он все равно будет проходить через остальную часть кода, в отличие от тех, у вас есть операторы if-else.

Если это так, то должен ли я предположить, что из того, что я получу из этого кода, это будет лучшее, худшее и среднее время обращения?

Правильно ли я понял?

public static int factorial(int number)
    {
        factorial = 1;                   // 1
        for (i = 1; i <= number; i++)    // 1+3n
            factorial = factorial * i;   // 2
        return factorial;                // 1
    }

Худший случай / Лучший случай: 3n + 5

Большой - O: О (п)

Ответы [ 3 ]

3 голосов
/ 27 июня 2011

Конечно.Большое О описывает верхнюю границу, а маленькое - нижнюю границу некоторой асимптотической величины (например, временную сложность алгоритма).На самом деле есть специальная нотация для определения границ, которые асимптотически тесны (это то, что вы получаете, когда Big o совпадает с маленькой o), которая называется большой тета-нотацией.

1 голос
/ 27 июня 2011

В этом случае сложность для серийного случая такая же, как и для наихудшего случая = O (n).Именно по той причине, которую вы указали.Независимо от того, что ввод, алгоритм всегда выполняет те же действия (нет, если / иначе).

1 голос
/ 27 июня 2011

В вашем случае, когда "number" зафиксировано, ваша программа не имеет худшего или лучшего случая - она ​​всегда делает "number" итераций, поэтому она имеет линейную сложность.
Для формальных математических определений см. Эти статьи:
http://en.wikipedia.org/wiki/Analysis_of_algorithms
http://en.wikipedia.org/wiki/Big_O_notation

...