Асимптотическая сложность алгоритма

Необходимо найти первое вхождение буквы A в строке длины n. За какую асимптотику можно решить эту задачу?

Введите значение наибольшего целого числа, не превосходящего \(log_2 1234.\)

Для приведенного ниже кода, найдите асимптотику (PYTHON): def merge_sort(nums): if len(nums) > 1: mid = len(nums)//2 left = nums[:mid] right = nums[mid:] merge_sort(left) merge_sort(right) i = j = k = 0 while i < len(left) and j < len(right): if left[i] < right[j]: nums[k] = left[i] i+=1 else: nums[k] = right[j] j+=1 k+=1 while i < len(left): nums[k] = left[i] i+=1 k+=1 while j < len(right): nums[k] = right[j] j+=1 k+=1 Определите асимптотику данного алгоритма.

Дана строка длины n, состоящая из 0 и 1. Необходимо найти длину её наибольшей подстроки, состоящей только из 1. Например, для строки 101101001001111011 ответом является число 4. Для решения данной задачи на написана такая программа (PYTHON): S = input() n = len(S) ans = 0 for i in range(n): t = 0 while i + t < n and S[i + t] == '1': t += 1 ans = max(ans, t) print(ans) Определите асимптотику данного алгоритма.

Для приведенного ниже кода, найдите асимптотику (PYTHON): for i in range( n - 1 ): for j in range(n - 2, i - 1, -1): if (A[j] > A[j + 1]): c = A[j] A[j] = A[j + 1] A[j + 1] = c count += 1 Определите асимптотику данного алгоритма.

На вход подаётся список из 100 элементов, принимающих значения от 1 до n. Необходимо посчитать количество пар равных элементов в этом списке. За какую асимптотику можно решить эту задачу?

Число действий алгоритма выражается следующей суммой: n+2n+3n+…+n⋅n. Чему равна асимптотика этого алгоритма?

Дана строка длины n, состоящая из 0 и 1. Необходимо найти длину её наибольшей подстроки, состоящей только из 1. Например, для строки 101101001001111011 ответом является число 4. Для решения данной задачи на написана такая программа (PYTHON): S = input() n = len(S) ans = 0 i = 0 while i < n: t = 0 while i < n and S[i] == '1': i += 1 t += 1 ans = max(ans, t) i += 1 print(ans) Определите асимптотику данного алгоритма.

Ботаник Игорь выращивает бамбук. В день покупки бамбук имел высоту h сантиметров. Каждый день в одно и то же время Игорь заходит в теплицу и измеряет новую высоту бамбука. Оказалось, что за сутки высота бамбука увеличивается вдвое плюс ещё на один сантиметр, то есть если высота была x сантиметров, то через сутки она будет 2x+1 сантиметр. Сегодня высота бамбука составила n сантиметров, при этом изначальная высота h была чётным натуральным числом. Вам известна текущая высота бамбука n, начальная высота h — не известна. Определите сколько дней прошло с момента покупки бамбука. За какую асимптотику можно решить эту задачу?

Необходимо транспонировать квадратную матрицу размера n (то есть в таблице n×n, заполненной числами, необходимо поменять местами элементы, симметричные относительно главной диагонали). За какую асимптотику можно решить эту задачу?