Что такое BigO notation ?
Спросят с вероятностью 10%
Big O notation - это математическая нотация, которая используется в анализе алгоритмов и служит для описания временной и пространственной сложности выполнения алгоритма. Она помогает оценить, насколько быстро или медленно алгоритм растет с увеличением размера входных данных.
Big O notation обозначается как O(f(n)), где f(n) - это функция, описывающая рост времени выполнения или используемой памяти в зависимости от размера входных данных (n). Например, если алгоритм выполняется за время, пропорциональное n^2, то его временная сложность будет O(n^2).
Вот некоторые из наиболее распространенных классов сложности:
1️⃣ O(1): Константная сложность. Время выполнения алгоритма не зависит от размера входных данных. Примером может служить доступ к элементу массива по индексу.
2️⃣ O(log n): Логарифмическая сложность. Время выполнения алгоритма логарифмически зависит от размера входных данных. Примером может служить бинарный поиск в отсортированном массиве.
3️⃣ O(n): Линейная сложность. Время выполнения алгоритма линейно зависит от размера входных данных. Примером может служить итерация по всем элементам в массиве.
4️⃣ O(n log n): Линейно-логарифмическая сложность. Примером может служить сортировка слиянием.
5️⃣ O(n^2): Квадратичная сложность. Время выполнения алгоритма квадратично зависит от размера входных данных. Примером может служить вложенные циклы с полным проходом по всем элементам вложенного массива.
6️⃣ O(2^n): Экспоненциальная сложность. Время выполнения алгоритма экспоненциально зависит от размера входных данных. Примером может служить задача о коммивояжере с использованием метода полного перебора.
Big O notation помогает анализировать и сравнивать эффективность алгоритмов и выбирать наиболее подходящий вариант для конкретной задачи.
➡️ Примеры ответов
➡️ Список всех вопросов на Python Developer
🧩 Идущий | 🔐 Собесы | 🔐 Тестовые
Спросят с вероятностью 10%
Big O notation - это математическая нотация, которая используется в анализе алгоритмов и служит для описания временной и пространственной сложности выполнения алгоритма. Она помогает оценить, насколько быстро или медленно алгоритм растет с увеличением размера входных данных.
Big O notation обозначается как O(f(n)), где f(n) - это функция, описывающая рост времени выполнения или используемой памяти в зависимости от размера входных данных (n). Например, если алгоритм выполняется за время, пропорциональное n^2, то его временная сложность будет O(n^2).
Вот некоторые из наиболее распространенных классов сложности:
1️⃣ O(1): Константная сложность. Время выполнения алгоритма не зависит от размера входных данных. Примером может служить доступ к элементу массива по индексу.
2️⃣ O(log n): Логарифмическая сложность. Время выполнения алгоритма логарифмически зависит от размера входных данных. Примером может служить бинарный поиск в отсортированном массиве.
3️⃣ O(n): Линейная сложность. Время выполнения алгоритма линейно зависит от размера входных данных. Примером может служить итерация по всем элементам в массиве.
4️⃣ O(n log n): Линейно-логарифмическая сложность. Примером может служить сортировка слиянием.
5️⃣ O(n^2): Квадратичная сложность. Время выполнения алгоритма квадратично зависит от размера входных данных. Примером может служить вложенные циклы с полным проходом по всем элементам вложенного массива.
6️⃣ O(2^n): Экспоненциальная сложность. Время выполнения алгоритма экспоненциально зависит от размера входных данных. Примером может служить задача о коммивояжере с использованием метода полного перебора.
Big O notation помогает анализировать и сравнивать эффективность алгоритмов и выбирать наиболее подходящий вариант для конкретной задачи.
➡️ Примеры ответов
➡️ Список всех вопросов на Python Developer