4430
правок
Задача об упаковке в контейнеры: различия между версиями
Материал из WEGA
м
→Экспериментальные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| (не показана 1 промежуточная версия этого же участника) | |||
| Строка 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. | ||
== Применение == | == Применение == | ||
| Строка 161: | Строка 161: | ||
== Экспериментальные результаты == | == Экспериментальные результаты == | ||
Данная задача является благодатной почвой для экспериментального анализа, и многие из приведенных выше теорем были впервые предположены на основе экспериментальных результатов. Например, эксперименты, описанные в [ ], послужили основой для теорем 10 и 12, а исследования в [ ] – для теоремы 14. | Данная задача является благодатной почвой для экспериментального анализа, и многие из приведенных выше теорем были впервые предположены на основе экспериментальных результатов. Например, эксперименты, описанные в работе [1], послужили основой для теорем 10 и 12, а исследования в [10] – для теоремы 14. | ||
== См. также == | == См. также == | ||
