Стратегически устойчивый метод нахождения временной сложности сложных алгоритмов? - PullRequest
Новая
       11

Стратегически устойчивый метод нахождения временной сложности сложных алгоритмов?

0 голосов
/ 09 ноября 2019

У меня есть вопрос, касающийся сложности времени (big-O) в Python. Я хочу понять общий метод, который мне нужно было бы реализовать при попытке найти биг-О сложного алгоритма. Я понял причину вычисления временной сложности простых алгоритмов, таких как цикл for, повторяющийся по списку из n элементов, имеющих O (n), или имеющий два вложенных цикла for, каждый повторяющийся по 2 спискам из n элементов, каждый из которых имеетбиг-о п ** 2. Но для более сложных алгоритмов, которые реализуют несколько операторов if-elif-else в сочетании с циклами for, я хотел бы посмотреть, есть ли стратегия, просто основанная на коде, итеративным способом, определить big-Oмой код, использующий простую эвристику (например, игнорирование постоянной постоянной сложности, если операторы или всегда возведение в квадрат n при переходе через цикл for, или выполнение чего-то определенного при встрече с оператором else).

Я создал игру на линкоре, для которого я хотел бы найти сложность времени, используя такую ​​вышеупомянутую стратегию. 


from random import randint

class Battle:
    def __init__(self):

        self.my_grid = [[False,False,False,False,False,False,False,False,False,False],[False,False,False,False,False,False,False,False,False,False],[False,False,False,False,False,False,False,False,False,False],[False,False,False,False,False,False,False,False,False,False],[False,False,False,False,False,False,False,False,False,False],[False,False,False,False,False,False,False,False,False,False],[False,False,False,False,False,False,False,False,False,False],[False,False,False,False,False,False,False,False,False,False],[False,False,False,False,False,False,False,False,False,False],[False,False,False,False,False,False,False,False,False,False]]

    def putting_ship(self,x,y):
        breaker = False
        while breaker == False:
            r1=x
            r2=y
            element = self.my_grid[r1][r2]

            if element == True:
                continue
            else:
                self.my_grid[r1][r2] = True
                break


    def printing_grid(self):
        return self.my_grid


    def striking(self,r1,r2):

        element = self.my_grid[r1][r2]
        if element == True:
            print("STRIKE!")
            self.my_grid[r1][r2] = False
            return True
        elif element == False:
            print("Miss")
            return False


def game():
    battle_1 = Battle()
    battle_2 = Battle()

    score_player1 = 0
    score_player2 = 0
    turns = 5

    counter_ships = 2

    while True:
        input_x_player_1 = input("give x coordinate for the ship, player 1\n")
        input_y_player_1 = input("give y coordinate for the ship, player 1\n")

        battle_1.putting_ship(int(input_x_player_1),int(input_y_player_1))



        input_x_player_2 = randint(0,9)
        input_y_player_2 = randint(0,9)


        battle_2.putting_ship(int(input_x_player_2),int(input_y_player_2))

        counter_ships -= 1
        if counter_ships == 0:
            break


    while True:
        input_x_player_1 = input("give x coordinate for the ship\n")
        input_y_player_1 = input("give y coordinate for the ship\n")

        my_var = battle_1.striking(int(input_x_player_1),int(input_y_player_1))

        if  my_var == True:
            score_player1 += 1
            print(score_player1)


        input_x_player_2 = randint(0,9)
        input_y_player_2 = randint(0,9)


        my_var_2 = battle_2.striking(int(input_x_player_2),int(input_y_player_2))

        if  my_var_2 == True:
            score_player2 += 1
            print(score_player2)

        counter_ships -= 1
        if counter_ships == 0:
            break


    print("the score for player 1 is",score_player1)
    print("the score for player 2 is",score_player2)





print(game())

Ответы [ 2 ]

0 голосов
/ 09 ноября 2019

Если это просто вложенные циклы for и операторы if / else, вы можете воспользоваться подходом, предложенным ibonyun - предположите, что все случаи if / else покрыты, и посмотрите на самые глубокие циклы (зная, что некоторые операциинапример, сортировка или копирование массива может скрывать собственные циклы.)

Однако в вашем коде также есть циклы while. В этом конкретном примере их не слишком сложно заменить на for s, но для кода, содержащего нетривиальные while s, не существует общей стратегии, которая всегда будет давать вам сложность - это является следствием проблемы остановки .

Например: 

def collatz(n):
    n = int(abs(n))
    steps = 0
    while n != 1:
        if n%2 == 1:
            n=3*n+1
        else:
            n=n//2
        steps += 1
        print(n)
    print("Finished in",steps,"steps!")

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

Примечание: вместо разбивания экрана 

self.my_grid = [[False,False,...False],[False,False,...,False],...,[False,False,...False]]

рассмотрим что-то вроде: 

grid_size = 10
self.my_grid = [[False for i in range(grid_size)] for j in range(grid_size)]

, который легче читать ипроверьте.

0 голосов
/ 09 ноября 2019

Эмпирический: Вы могли бы провести несколько временных испытаний, увеличив n (так, может быть, увеличив размер доски?) И построить результирующие данные. По кривой / наклону линии можно определить сложность времени.

Теоретически: проанализировать скрипт и отследить наибольшее значение O (), найденное для любой данной строки или вызова функции. Любые операции сортировки дадут вам лог. Цикл for внутри цикла for даст вам n ^ 2 (при условии, что они оба перебирают входные данные) и т. Д. Сложность времени заключается в широких штрихах. O (n) и O (n * 3) - это линейное время, и это то, что действительно имеет значение. Я не думаю, что вам нужно беспокоиться о мелочах всей вашей логики if-elif-else. Может быть, просто сосредоточиться на худшем случае?

...