Наилучшее и наихудшее время выполнения в тета-записи - PullRequest
Новая
       26

Наилучшее и наихудшее время выполнения в тета-записи

0 голосов
/ 27 марта 2012

Я не ищу здесь ответ, а просто как найти наихудший / лучший случай следующей проблемы (в тета-записи); Циклы for обычно (theta (n)), что делает лучший и худший случай, но я думаю, что здесь происходит что-то еще. Любая помощь будет оценена. 

Input: x (an integer), n (an integer)
addOnes(x, n) {
    if x > n then 
        for i <- 1 to n 
            return x + n
    else 
        for i <- x to n
                x <- x + n
    return x

Редактировать ответ:

Из-за возврата x + n константа (theta (1)) будет лучшей.

Best = (тета (1)) Худший = (тета (н))

1 Ответ

0 голосов
/ 27 марта 2012

Есть две ветви, и обе достижимы. Чтобы найти сложность наилучшего и наихудшего случая в целом, найдите сложность наилучшего и наихудшего случая для каждого цикла, тогда сложность наилучшего случая в целом является лучшей из сложностей наилучшего случая для двух ветвей. Аналогично для худшего случая сложности. И в проблему встроена небольшая ошибка, чтобы наивный мог споткнуться, так что будьте бдительны.

...