В алгоритмах «разделяй и властвуй», таких как быстрая сортировка и сортировка слиянием, ввод обычно (по крайней мере, во вводных текстах) делится на две части , и два меньших набора данных затем обрабатываются рекурсивно. Для меня имеет смысл, что это ускоряет решение проблемы, если две половины...
У меня есть следующий алгоритм, который находит дубликаты и удаляет их: public static int numDuplicatesB(int[] arr) { Sort.mergesort(arr); int numDups = 0; for (int i = 1; i < arr.length; i++) { if (arr[i] == arr[i - 1]) { numDups++; } } return numDups; } Я пытаюсь найти наихудший случай...
Какой термин я могу использовать для описания чего-либо со сложностью O (N log N)? Например: O (1): постоянная O (log N): логарифмический O (N): линейный O (N log N): ?????? O (N 2 ): квадратичный O (N 3 ): кубический...
Я всегда слышал, что линейный поиск - это наивный подход, и бинарный поиск лучше, чем он, по производительности из-за лучшей асимптотической сложности. Но я никогда не понимал, почему это лучше, чем линейный поиск, когда перед двоичным поиском требуется сортировка? Линейный поиск есть O(n)и...
Я программист и только начал читать Алгоритмы. Я не полностью убежден с примечаниями, а именно, Бог О, Большая Омега и Большая Тета. Причина в том, что по определению Большого О он утверждает, что должна быть функция g (x), такая, что она всегда больше или равна f (x). Или f (x) <= cn для всех...
Я проходил анализ быстрой сортировки в книге Алгоритмов Седжвика. Он создает следующее рекуррентное отношение для числа сравнений в быстрой сортировке при сортировке массива из N различных элементов. Мне тяжело понять это ... Я знаю, что для любого элемента требуется 1 / N вероятность того, что он...
Я решаю вопрос об алгоритме, и мой анализ состоит в том, что он будет работать на O (2 ^ sqrt (n)). Насколько большой это? Это соответствует O (2 ^ n)? Это все еще неполиномиальное...
Недавно я реализовал алгоритм расстояния Дамерау-Левенштейна из псевдокода в Википедии. Я не мог найти никакого объяснения того , как именно она работает и псевдокод использует имена полностью неинформативные переменные , как DA, DB, i1, и j1что оставил меня почесал голову. Вот моя реализация в...