Рекомендации по асимптотическому анализу

Опубликовано: 22 Сентября, 2022

В этой статье основное внимание уделяется изучению некоторых правил, которые могут помочь определить время работы алгоритма.

Асимптотический анализ относится к вычислению времени выполнения любой операции в математических единицах вычисления. В асимптотическом анализе производительность алгоритма оценивается с точки зрения размера входных данных (мы не измеряем фактическое время выполнения). Также рассчитывается, как время (или пространство), занимаемое алгоритмом, увеличивается с размером входных данных.

(g(n)) = {f(n) such that g(n) is a curve which approximates f(n) at higher values of input size, n}
This curve is called asymptotic curve and the algorithm analysis for such a curve is called Asymptotic analysis.

Циклы : время выполнения цикла — это не более чем время выполнения операторов внутри цикла, включая тесты), умноженное на количество итераций.

Ниже приведена программа на Python, которая демонстрирует описанную выше концепцию:

Python3

# Python program to implement
# the above concept
# execute n times for in
# range(0.00);
 
for i in range(0, n):
print ("Current Number:", i, sep = "")

#constant time 
Total time a constant cx n = cn = O(n).

Вложенные циклы : анализ изнутри. Общее время выполнения равно произведению размеров всех циклов.

Ниже приведена программа на Python, которая демонстрирует описанную выше концепцию:

Python3

# Python program to implement
# the above concept
# outer loop executed n times
for i in range(0, n):
 
    # inner loop executes n times
    for j in range(0, n):
      print("i value % d  and j value % d" % (i, j))

# constant time 
Total time = C x n x n = cn^2 =0(n²).

Последовательные операторы : добавьте временную сложность каждого оператора.

Ниже приведена программа на Python, которая демонстрирует описанную выше концепцию:

Python3

# Python program that implements
# the above concept
n = 100
 
# executes n times
for i in range (0, n):
    print (Current Number: i, sep = "")
     
    # outer loop executed n times
    for i in range (0, n):
       
      # inner loop executes n times
      for j in range(0, n):
        print(" i value % d and j value % d"%(i, j))
 
X

Total time = co + c1n + c2n^2 = 0(n^2).

Заявления if-then-else : время выполнения в наихудшем случае: тест плюс либо часть then части else, в зависимости от того, какая из них больше.

Ниже приведена программа на Python, которая демонстрирует описанную выше концепцию:

Python3

# Python program that implements
# the above concept
if n == I:
  print ("Incorrect Value")
  print (n)
 
else:
  for i in range(0, n):
     
    # constant time
    print (CurrNumber:, i, sep = "")

Total time = co + c1*n = 0(n).

Алгоритмы

Рекомендации по асимптотическому анализу

Python3

Python3

Python3

Python3

РЕКОМЕНДУЕМЫЕ СТАТЬИ