Публикации по теме 'big-o'


Бинарный поиск и его большая буква "О"
Двоичный поиск может быть значительно лучше линейного поиска, если говорить о временной сложности поиска (учитывая, что массив отсортирован). Вместо того, чтобы удалять один за другим элемент на каждом шаге, мы можем удалить половину элемента за один шаг. Кодовое решение В приведенном выше примере (строка 14) как выполняется этот поиск: step1 . [2,5,6, 9 ,13,15,28,30] //=>mid value is: 9 target is : 30 step2 . [13, 15 ,28,30] //=> mid value is: 15 target is :..

Вопросы по теме 'big-o'

Временная сложность Special Double For-Loop?
Мне только что задали этот вопрос на экзамене, и это сводит меня с ума. Вопрос заключается в следующем: какова временная сложность следующего кода с точки зрения n: int count = 0; for(int i = 0; i < n; i++) { for(int j = 1; j < n; j = j...
72 просмотров
schedule 06.03.2024

Временная сложность вложенного цикла while
Я не понимаю, как определить временную сложность цикла while в этом утверждении: procedure P (integer n); for (i: 1 to n) x := n; while (x > 0) x := x - i; Я знаю, что цикл for выполняется (n-1) раз. Сначала я думал, что...
2334 просмотров
schedule 28.04.2024

Версия нотации Big-O, включающая параллелизм?
Этот вопрос требует некоторой подготовки. http://igoro.com/archive/big-oh-in-the-parallel-world/ «Метод 1» в этой ссылке подробно описывает нотацию для описания влияния параллелизма на алгоритмическую временную сложность. Мне очень нравится...
169 просмотров

Временная сложность решения задачи обогревателя на Leetcode
Учитывая это решение python из популярного вопроса о Leetcode: def findOptimalRadius(houses, heaters): houses.sort() heaters.sort() last = len(heaters) - 1 x1,x2 = 0,0 res = 0 for house in houses:...
69 просмотров
schedule 31.05.2024