Понимание того, когда использовать тета для временной сложности
Чтобы разбить его немного больше, он имеет много общего с двоичным представлением рассматриваемого значения.
For example (in decimal): x = 8 y = 1 would come out to (in binary): x = 1000 y = 0001 From there, you can do computational operations such as 'and' or 'or'; in this case: x | y = 1000 0001 | ------ 1001 or...9 in decimal
Надеюсь, это поможет.
1 ответ
По сути, вы можете использовать Big-only только в том случае, если между верхней и нижней границами времени выполнения алгоритма нет асимптотического разрыва:
В вашем примере сортировка вставкой занимает максимум O (n ^ 2) время (в худшем случае) и занимает Ω (n) время (в лучшем случае). Итак, O (n ^ 2) - верхняя граница времени алгоритма, а Ω (n) - нижняя граница алгоритма. Поскольку эти два не совпадают, вы не можете использовать Big-Θ для описания времени выполнения алгоритма сортировки вставок.
Однако рассмотрим алгоритм Selection-Sort . Время его наихудшего времени работы равно O (n ^ 2), а время наработки в лучшем случае - Ω (n ^ 2). Следовательно, поскольку верхняя граница и нижняя граница совпадают (асимптотически), можно сказать, что время выполнения алгоритма сортировки выбора равно Θ (n ^ 2).