Подсчет долин из последовательности шагов, где каждый шаг - «U» или «D». Какова временная сложность этого решения? - PullRequest
Новая
       60

Подсчет долин из последовательности шагов, где каждый шаг - «U» или «D». Какова временная сложность этого решения?

0 голосов
/ 28 марта 2020

Учитывая последовательность шагов вверх и вниз. Найдите и верните количество долин в заданной последовательности. Мы всегда начинаем и заканчиваем на уровне моря, и каждый шаг вверх или вниз представляет собой единицу изменения высоты.

  • Гора - это последовательность последовательных шагов над уровнем моря, начиная с шага вверх от Уровень моря и заканчивающийся шагом вниз до уровня моря
  • Долина - это последовательность последовательных шагов ниже уровня моря, начиная с шага вниз от уровня моря и заканчивая шагом вверх до уровня моря.

Пример: Если путь 'DDUUUUDD', сначала мы входим в долину глубиной в две единицы. Затем мы поднимаемся на гору высотой в две единицы. Наконец мы возвращаемся к уровню моря. Поэтому мы возвращаем единицу.

Вопрос: Является ли временная сложность данного решения O (n / 2) или O (n), и как оператор if изменяет сложность алгоритм?

Решение: 

def countingValleys(n, s):

altitude = 0
prev_a = 0
v_count = 0

for i in range(1, n, 2):
    if s[i] == s[i-1]:
        if s[i] == 'D':
            altitude -= 2
            prev_a = altitude + 1
        else:
            altitude += 2
            prev_a = altitude - 1
    else:
        if s[i] == 'D':
            prev_a = altitude + 1
        else:
            prev_a = altitude - 1

    if altitude == 0 and prev_a == -1:
        v_count += 1

return v_count

1 Ответ

1 голос
/ 28 марта 2020

В обозначении Bi gO не учитывается фактор 1/2. O(n) и O(n/2) по-прежнему O (n) - хотя на практике это может быть немного быстрее.

Ваша проблема должна касаться каждого элемента один раз, чтобы его O (n) - наличие if s на самом деле не влияет на это.

Если вы хотите практичный более быстрый способ сделать что-то, сравните это. Читайте о модуле timeit здесь: https://docs.python.org/3.8/library/timeit.html

См .: https://en.wikipedia.org/wiki/Big_O_notation

Вы также можете упростить свою реализацию: 

def countingValleys(string):
    """returns number of sea levels touched and current level 
    as tuple (sealevels_touched, current_level)"""
    level = 0
    valleys = 0
    for c in string:
        if c == "D":
            if level == 0:
                valleys += 1
            level -= 1 
        else:  
            level += 1

    return valleys 

print(countingValleys("DDUDDUUUUUUDDDUDUUDUUDUUUDDDDDD")) # 2
print(countingValleys("DDUUDUUD")) # 2

Нет необходимости перечислять или индексировать вообще.

...