Python Codility Frog River Один раз сложность - PullRequest
Новая
       8

Python Codility Frog River Один раз сложность

0 голосов
/ 28 сентября 2018

Так что это еще один подход к, вероятно, известной платформе кодилизации, задача о лягушке, пересекающей реку.И извините, если этот вопрос задан неправильно, это мой первый пост здесь.

Цель состоит в том, чтобы найти самое раннее время, когда лягушка может прыгнуть на другую сторону реки.Например, если X = 5 и массив A такой, что: 

  A[0] = 1
  A[1] = 3
  A[2] = 1
  A[3] = 4
  A[4] = 2
  A[5] = 3
  A[6] = 5
  A[7] = 4

функция должна вернуть 6.

Пример теста: (5, [1, 3, 1, 4, 2, 3, 5, 4])

Полный текст задания: https://app.codility.com/programmers/lessons/4-counting_elements/frog_river_one/

Итак, это был мой первый очевидный подход: 

def solution(X, A):
    lista = list(range(1, X + 1))
    if X < 1 or len(A) < 1:
        return -1
    found = -1
    for element in lista:
        if element in A:
            if A.index(element) > found:
                found = A.index(element)
        else: return -1
    return found

X = 5
A = [1,2,4,5,3]
solution(X,A)

Это решение на 100% правильно и получает 0% в тестах производительности.

Поэтому я подумал, что меньше строк + понимание списка получат лучший результат: 

def solution(X, A):
    if X < 1 or len(A) < 1:
        return -1
    try:
        found = max([ A.index(element) for element in range(1, X + 1) ])
    except ValueError:
        return -1
    return  found

X = 5
A = [1,2,4,5,3]
solution(X,A)

Это также работает иимеет 0% производительности, но все равно быстрее.

Я также нашел решение от deanalvero (https://github.com/deanalvero/codility/blob/master/python/lesson02/FrogRiverOne.py):

def solution(X, A):
    # write your code in Python 2.6
    frog, leaves = 0, [False] * (X)
    for minute, leaf in enumerate(A):
        if leaf <= X:
            leaves[leaf - 1] = True
        while leaves[frog]:
            frog += 1
            if frog == X: return minute
    return -1

Это решение получает 100% тестов на правильность и производительность.

Мой вопрос возникает, вероятно, из-за того, что я не совсем понимаю сложность этого времени. Пожалуйста, скажите, как последнее решение лучше моего второго решения? У него есть цикл while для цикла! Он должен быть медленным, но это не так.

Ответы [ 2 ]

0 голосов
/ 14 ноября 2018

Ключ в том, что оба ваших начальных решения являются квадратичными.Они включают в себя O (n) внутреннего сканирования для каждого родительских элементов (в результате O (n ** 2)).

Быстрое решение изначально постигнет та же участь, что и егоОчевидно, он содержит цикл внутри цикла.Но внутренний цикл while не полностью сканируется для каждого «листа».Посмотрите, где инициализируется «лягушка», и вы заметите, что цикл while эффективно определяет, где он остановился для каждого листа.

0 голосов
/ 28 сентября 2018

Количество вложенных циклов напрямую не говорит вам о сложности времени.Пусть n будет длиной входного массива.Внутри цикла while требуется среднее O (1) время, хотя сложность времени в худшем случае составляет O (n) .Быстрое решение использует логический массив листьев , где для каждого индекса оно имеет значение true , если есть лист, и false в противном случае.Внутренняя часть цикла while в течение всего процесса согласования увеличивается не более n раз.Внешний цикл for также выполняется только n раз.Это означает, что временная сложность алгоритма составляет O (n) .

...