В настоящее время я учусь в магистратуре и практикую различные алгоритмические c вопросы. Я стараюсь анализировать сложность времени и пространства для каждого вопроса. Однако у меня есть сомнения:
Если в алгоритме есть два шага (шаги, которые вызывают рекурсивные функции для изменения размера OP), то есть
int a = findAns(arr1)
int b = findAns(arr2)
return max(a,b);
Будет ли худшая временная сложность этого: O(N1) + O(N2) или просто O(max(N1,N2)). Я спрашиваю, потому что за один раз мы будем вызывать функцию только с одним входным массивом.
При вычислении сложности пространства наихудшего случая, если она окажется, O(N) + O(logN), начиная с N > logN, мы бы отбросили O(logN) или, поскольку logN также зависит от N и говорят, что наихудшая сложность пространства равна O(N), мы бы сказали, наихудшая сложность пространства равна всего лишь O(N).