У меня есть большая проблема понимания сложности и особенно с binary trees.Сложность и двоичные попытки
Например, я знаю, что когда у нас есть проблема, скажем, размер проблемы x=log2(sizeofarray), но я не понимаю, откуда это происходит: log2?
Это журнал потому что каждый уровень дерева разбивает вашу проблему на две части.
Например, рассмотрим этот набор данных:
{ 1, 2, 3, 4, 5, 6, 7, 8 }
Первый уровень может быть
{ 1, 2, 3, 4 }, { 5, 6, 7, 8 }
второй уровень:
{ 1, 2 }, { 3, 4 }, { 5, 6 }, { 7, 8 }
третий уровень:
{ 1 }, { 2 }, { 3 }, { 4 }, { 5 }, { 6 }, { 7 }, { 8 }
Здесь с 8 значениями, бревенчатый (8) = 3, и есть 3 уровня в дереве.
Также см эти другие вопросы StackOverflow больше:
Давайте рассмотрим двоичный поиск в качестве простого примера. Скажем, у вас есть отсортированный список из 64 элементов, и вы ищете какой-то конкретный. На каждой итерации вы уменьшаете вдвое набор данных. К тому времени ваш набор данных имеет 1 элемент, вы в два раза его 6 раз (COUNT стрелки, а не числа):
64 -> 32 -> 16 -> 8 -> 4 -> 2 -> 1
Причиной этого является тот факт, что 64 = 2^6, где 2 является базой (разделить набор данных в 2 части на каждой итерации), а показатель - 6 (как вы дойдете до дна в 6 итераций). Существует еще один способ, чтобы написать это, так как экспоненцирование имеет обратный логарифм:
64 = 2^6
6 = log2 64
Таким образом, мы можем видеть, что число итераций масштабируется с основанием два логарифм числа элементов.
спасибо, а как насчет этого наилучшего/наихудшего сценария? можем ли мы сказать, что если элемент, который мы ищем, находится на общем дне, сложность - log2 (размер), и если он наверху, то это O (1)? – pengj
В худшем случае вам нужно путешествовать по * целому * дереву, что дает вам сложность O (размер), где размер - это количество узлов в дереве, нет журнала в этом случае – user2314737
Как правильно указывает @ user2314737, худший случай - это [вырожденное дерево] (http://en.wikipedia.org/wiki/Binary_tree#Types_of_binary_trees), который в основном является [связанным списком] (http://en.wikipedia.org/wiki/Linked_list). –