Публикации по теме 'big-o'
Обозначение Big O стало легко усваиваемым.
Создавать приложения на javascript - это хорошо, но хороший разработчик думает в первую очередь о производительности, потому что, если пользователю приходится ждать выполнения запрошенных операций, а система слишком долго отвечает, пользователь перезагрузится несколько раз или уйдет. сайт в конце концов.
Приятный и чистый код - это не решение, позволяющее приложениям работать достаточно хорошо, они должны кодировать таким образом, чтобы уменьшить количество операций и время, которое они..
Big O 101 — Взгляд на поверхность
Я буду максимально простым, тем более, что есть много других ссылок, которые вы можете найти в Google, чтобы углубиться, и основное внимание в этом руководстве будет уделено знакомству с основами Big O для настройки интервью.
Как правило, вас спросят о временной сложности и пространственной сложности вашего кода (или кода в целом), чтобы увидеть, можете ли вы понять, считается ли он несколько эффективным или нет, и можно ли его оптимизировать, чтобы он работал быстрее или занимал больше..
Структуры данных и алгоритмы (DSA) с использованием JavaScript — Big O Notation
Предпосылки
JavaScript
Цели
Мотивируйте потребность в чем-то вроде Big O Notation Опишите, что такое нотация Big O Упростите выражения Big O Дайте определение «временной сложности» и «пространственной сложности». Оцените временную и пространственную сложность различных алгоритмов, используя нотацию Big O. Расскажите, что такое логарифм.
Представьте, что у нас есть несколько реализаций одной и той же задачи. Как мы можем определить, какая из них является «лучшей»?..
Разъяснение сложности Большого О - Часть 1
В сегодняшнем мире нетерпения как никогда важно иметь эффективный код в наших приложениях. Сложность по времени разрабатываемых нами алгоритмов - это концепция, которую необходимо усвоить, чтобы серьезно воспринимать ее в современном мире кода. Итак, как мы его анализируем и измеряем? Просто… с большой буквы…
Так что же такое Big O? Это стандарт обозначений, который описывает время выполнения (или эффективность) алгоритма в зависимости от его входного размера.
Термин Big O..
Вопросы по теме 'big-o'
Домашнее задание по нотации Big O - анализ алгоритма фрагмента кода?
В качестве домашнего задания мне дали следующие 8 фрагментов кода для анализа и определения времени выполнения в нотации Big-Oh. Кто-нибудь может сказать мне, на правильном ли я пути?
//Fragment 1
for(int i = 0; i < n; i++)
sum++;
Я...
18153 просмотров
schedule
22.04.2024
сложность мультимножества, карты и хеш-карты
Я хотел бы знать сложность нотации Big O классов мультимножества STL, карт и хэш-карт, когда:
вставка записей
доступ к записям
получение записей
сравнение записей
66032 просмотров
schedule
30.12.2023
Почему вставка в конец динамического массива O (1), а вставка в середине - O (n)?
Согласно статье Википедии о динамических массивах , вставка / удаление в конце массива - O (1) при вставке / удалении с середины - O (n). Почему именно так?
Также - если у меня есть динамический массив с 5 элементами, и я вставляю новый элемент...
3749 просмотров
schedule
07.05.2024
Каково значение O для наивного случайного выбора из конечного множества?
Этот вопрос о получении случайных значений из конечного набора заставил меня задуматься...
Довольно часто люди хотят получить X уникальных значений из набора значений Y. Например, я могу захотеть сдать руку из колоды карт. Я хочу 5 карт, и я...
1834 просмотров
schedule
03.10.2022
Есть ли способ умножения матриц, имеющих сложность O (n)?
Я хочу умножить две матрицы, но тройной цикл имеет сложность O(n 3 ). Есть ли в динамическом программировании алгоритм для умножения двух матриц со сложностью O(n)?
хорошо, мы не можем получить лучше, чем O(n 2.81 )
редактировать: но есть ли...
5754 просмотров
schedule
09.01.2024
Каковы различия между O (1) и O (2) в алгоритмическом анализе?
Согласно определению большого O f(n) <= C*g(n) (что означает f(n) = O(g(n) ), можно сделать вывод, что:
f(n) <= C
f(n) <= 2C
Я думаю, что между этими двумя нет большой разницы. Что я мог придумать, так это:
f(n) = 1 - 1 / n...
4093 просмотров
schedule
05.12.2023
Доказательство большого O с sqrt и журналом
Мне трудно понять, как это доказать
t(n) = sqrt(31n + 12n log n + 57)
is
O(sqrt(n) log n)
Мне еще не приходилось иметь дело с квадратным корнем в большой нотации O, поэтому у меня много проблем с этим! Любая помощь приветствуется :)
5992 просмотров
schedule
21.02.2024
Пример непрактичного алгоритма, который, как известно, находится в P?
Общепризнано, что проблемы, которые можно решить за полиномиальное время, являются «разрешимыми», в то время как алгоритмы, требующие большего времени, неразрешимы. Конечно, возможность решения за полиномиальное время ничего не говорит об абсолютной...
489 просмотров
schedule
26.12.2023
Лучший алгоритм удаления дубликатов в массиве строк
Сегодня в школе учитель попросил нас реализовать алгоритм удаления дубликатов. Это не так сложно, и все придумали следующее решение (псевдокод):
for i from 1 to n - 1
for j from i + 1 to n
if v[i] == v[j] then remove(v, v[j]) //...
19353 просмотров
schedule
05.11.2023
Помогите проверить Big O
Привет, я пытаюсь проверить некоторые алгоритмы сортировки.
Сортировка вставками
Сортировка слиянием
Быстрая сортировка с разделением по медиане трех и отсечкой 10 (используя сортировку вставками для небольших частей массива)...
194 просмотров
schedule
11.02.2024
Является ли log (n) = Ω (n)?
Я считаю, что это не так. Определение таково:
log(n) >= c*n for some n = x, and all n > x
Причина, по которой я думаю, что это не так, заключается в том, что скорость роста c*n = c. Скорость роста log(n) = 1/n. Итак, поскольку n ->...
4673 просмотров
schedule
12.03.2024
Анализ Big-O с функциями внутри функций
Я не понимаю, как работает Big-O при работе с функциями внутри функций (при анализе наихудшего случая). Например, что, если у вас есть что-то вроде:
for(int a = 0; a < n; a++)
{
*some function that runs in O(n*log(n))*
for(int b = 0; b...
1702 просмотров
schedule
02.12.2023
Рисование дерева повторяемости и анализ
Я смотрю лекцию 1 Intro to Algorithms (MIT). Там что-то вроде ниже (анализ сортировки слиянием)
T(n) = 2T(n/2) + O(n)
Несколько вопросов:
Почему работа на нижнем уровне становится O(n) ? Там сказано, что граничный случай может...
146 просмотров
schedule
26.10.2023
Сопоставление числовых диапазонов с отдельными элементами с доступом O(1)
Вопрос простой, я хочу сопоставить каждое число от 0 до N-1 с числом элементов K ‹ N таким образом, что: 1,2,3,...,i-1 сопоставляется с элементом 1 i, i+1, i+2,...,i+k-1 сопоставляется элементу 2... и так далее, пока i+k+...+z, i+k+...+z+1, i+k+......
114 просмотров
schedule
09.12.2023
Понимание лямбды применительно к Главной теореме
Предположим, у меня есть такой случай, как T (n) = 2T (n/4) + 1. f(n)=1 a=2 и b=4. Таким образом, n^(1/2)>1. Это должен быть случай 1. Однако в случае 1 также есть лямбда, так что f (n) = O (n ^ ((1/2)-лямбда)) для некоторого лямбда> 0. В этом...
1625 просмотров
schedule
24.02.2024
Сложность обозначения BigO
Я задавал некоторые вопросы, но ответы не были предоставлены, поэтому мне было интересно, верны ли мои ответы.
а) учитывая, что a[i....j] — массив целых чисел с n элементами, а x — целое число
int front, back;
while(i <= j) {
front =...
202 просмотров
schedule
15.02.2024
Доказательство с большой ой
Только начинаю изучать большой и асимптотический анализ, и я застрял на этом конкретном доказательстве:
Как мы можем доказать, что 2^n равно O(n!)? Спасибо
327 просмотров
schedule
04.05.2024
Удаление элементов из списка - временная сложность алгоритма
Задача состоит из двух отсортированных списков без дубликатов размеров n и m. Первый список содержит строки, которые следует удалить из второго списка.
Самый простой алгоритм должен был бы выполнять nxm операции (я полагаю, что терминология для...
215 просмотров
schedule
23.04.2024
Временная сложность для сортировки Shell?
Во-первых, вот мой код сортировки Shell (с использованием Java):
public char[] shellSort(char[] chars) {
int n = chars.length;
int increment = n / 2;
while(increment > 0) {
int last = increment;
while(last < n) {...
43573 просмотров
schedule
07.12.2023
Дискретная математика Обозначение Big-O Сложность алгоритма
Я, вероятно, смогу понять часть б, если вы поможете мне сделать часть а. Я весь день смотрю на эту и подобные проблемы, и у меня просто проблемы с пониманием того, что делать с вложенными циклами. Для первого цикла n итераций, для второго n-1, для...
4567 просмотров
schedule
23.10.2022
