Как определить время выполнения для каждой строки в терминах «n» для программы? И общее время работы Big-O для всей программы? - PullRequest
Новая
       12

Как определить время выполнения для каждой строки в терминах «n» для программы? И общее время работы Big-O для всей программы?

0 голосов
/ 28 октября 2019

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

Я пытался использовать веб-сайты, но это все еще сбивает с толку. 

filename = input("Please enter file name: ")
file = open(filename, "r")
number = int(file.readline())

for line in file.readlines():
    new_number = int(line)
    if number > new_number:
        print ("Looks like", filename, "needs to be sorted")
        break
    number = new_number
else:
    print ("Congratulations! The file", filename, "is nicely sorted!")

file.close()

Результаты должны быть в формате n. например, O (n) или O (n ^ 2)

1 Ответ

0 голосов
/ 29 октября 2019

Анализ Big O используется, чтобы дать представление о том, как программа масштабируется при изменении пользовательского ввода.

Давайте начнем с основ: 


def foo(user_input):

       output = 5+5

       return output

Приведенный выше пример показывает, что независимо от того, какМой пользовательский ввод, будь то 5 или 5 миллиардов, моя программа будет работать с постоянной «скоростью». Это O (1), где 1 представляет собой константу. 

def foo(user_input):

    for i in range(user_input):
             print(i)

Теперь, что здесь происходит, это то, что время, необходимое для запуска нашей программы, определяется длиной ввода. Если у нас большой ввод, он занимает много времени, маленький ввод занимает мало времени. Корреляция такова, что время выполнения равно нашему user_input. Следовательно, большой O - это O (n), где n - длина пользовательского ввода. 

filename = input("Please enter file name: ")
file = open(filename, "r")
number = int(file.readline())

for line in file.readlines():
    new_number = int(line)
    if number > new_number:
        print ("Looks like", filename, "needs to be sorted")
        break
    number = new_number
     else:
        print ("Congratulations! The file", filename, "is nicely sorted!")

file.close()

Длина пользовательского ввода напрямую определяется количеством строк в файле. Если в файле n строк, он будет запущен n раз. Следовательно, большой O равен O (n).

Теперь вы можете спросить: «А как насчет оператора IF и печати? Он также добавляет время программе, даже если его наносекунды времени»

Все остальное, что вы делаете в цикле for, не изменяется при вводе пользователем. На самом деле, это постоянно. Так что это будет записано как O (n + 1). Но дело в том, что если n равно миллиону, миллион + 1 не имеет значения, так как это занимает практически то же время. Следовательно, мы игнорируем любые константы (включая мультипликативные константы, такие как O (3n)), чтобы привести к O (n).

...