4652
правки
Задача об упаковке в контейнеры: различия между версиями
Перейти к навигации
Перейти к поиску
м
Задача об упаковке в контейнеры (посмотреть исходный код)
Версия от 09:53, 12 марта 2024
, 12 марта 2024→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 123: | Строка 123: | ||
Теорема 12 [2, 14]. | '''Теорема 12 [2, 14].''' | ||
1. Для <math>0 < b \le 1/2</math> '''и''' <math>A \in \{FFD, BFD\}</math> выполняется <math>EW^n_A(U(0, b]) = O(1).</math> | '''1. Для <math>0 < b \le 1/2</math> '''и''' <math>A \in \{FFD, BFD\}</math> выполняется <math>EW^n_A(U(0, b]) = O(1).</math>''' | ||
2. Для <math>1/2 < b < 1</math> '''и''' <math>A \in \{FFD, BFD\}</math> выполняется <math>EW^n_A(U(0, b]) = \Theta(n^{1/3}).</math> | '''2. Для <math>1/2 < b < 1</math> '''и''' <math>A \in \{FFD, BFD\}</math> выполняется <math>EW^n_A(U(0, b]) = \Theta(n^{1/3}).</math>''' | ||
3. Для <math>0 < b < 1</math> выполняется <math>EW^n_{OPT}(U(0, b]) = O(1).</math> | '''3. Для <math>0 < b < 1</math> выполняется <math>EW^n_{OPT}(U(0, b]) = O(1).</math>''' | ||
| Строка 148: | Строка 148: | ||
'''Теорема 14 [9]. Для любого дискретного распределения F справедливы следующие утверждения:''' | '''Теорема 14 [9]. Для любого дискретного распределения F справедливы следующие утверждения:''' | ||
'''1. Если <math>EW^n_{OPT}(F) = \Theta(\sqrt{n})</math>, то <math>EW^n_{SS}(F) = \Theta(\sqrt{n}) | '''1. Если <math>EW^n_{OPT}(F) = \Theta(\sqrt{n})</math>, то <math>EW^n_{SS}(F) = \Theta(\sqrt{n});</math>''' | ||
'''2. Если <math>EW^n_{OPT}(F) = O(1)</math>, то <math>EW^n_{SS}(F) \in \{ O(1), \Theta(log \; n) \}.</math>''' | '''2. Если <math>EW^n_{OPT}(F) = O(1)</math>, то <math>EW^n_{SS}(F) \in \{ O(1), \Theta(log \; n) \}.</math>''' | ||
'''Кроме того, простая модификация SS позволяет исключить | '''Кроме того, простая модификация SS позволяет исключить член <math>\Theta(log \; n)</math> в условии 2. | ||
== Применение == | == Применение == | ||