В поисках лучшего и худшего O () - PullRequest
Новая
       5

В поисках лучшего и худшего O ()

0 голосов
/ 20 июня 2019

Используя следующий алгоритм, я пытаюсь определить наилучшее и наихудшее O (). 

minCoin(total, C[]) {
    if (total == 0) {return 0}
    min = MAX_VALUE
    for (i in C.length) {
        if (C[i] > total) {continue}
        value = minCoin(total - C[i], C)
        if (value < min) {min = value}
    }
    min = MAX_VALUE ? min : min++
    return min
}

Наилучшее: O (1), потому что если итоговое значение == 0, вернем худшее: O (nT)потому что n = количество монет в массиве, а T = общая сумма, которую мы делаем.

Я также подумал, что наихудший случай может быть O (2 ^ n), где n - количество рекурсивных вызовов.

Это правильно?

1 Ответ

2 голосов
/ 20 июня 2019

В настоящее время сложность составляет около O (2 ^ n). Так что это экспоненциально.
Но если вы преобразуете его в динамическое программирование путем запоминания, сложность будет O (nT).

Решение с помощью динамического программирования: 

memoization[total]={-1}// initially every index holds -1
minCoin(total, C[]) {
    if (total == 0) {return 0}

    if(memoization[total]!=-1) return memoization[total]; 
    min = MAX_VALUE
    for (i in C.length) {
        if (C[i] > total) {continue}
        value = minCoin(total - C[i], C)
        if (value < min) {min = value}
    }
    min = MAX_VALUE ? min : min++
    return memoization[total]=min 
}

Как только мы вычислили итог, мы изменили значение запоминания итога с -1 на его результат. Поэтому, если мы снова получим итоговое значение, мы просто вернем памятку [итого], так как мы сохранили результат на ней раньше.

Подробнее о DP: https://www.geeksforgeeks.org/dynamic-programming/

...