Как определить сложность кода python? - PullRequest
Новая
       6

Как определить сложность кода python?

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

Мне нужно понять сложность следующего кода. Я знаком с концепциями всех обозначений Big O (), а также читал много блогов, но не могу понять, как их применять в больших программах. Ниже приведен код наибольшего числа паллиндромов от 100 до 999: 

def isPaindrome(number):
    stringNum = str(number)
    firstDigit_index,lastDigit_index=0,len(stringNum)-1
    isPalindrome = False
    while(lastDigit_index > 0 and firstDigit_index < lastDigit_index):
        #print(stringNum[f],"==",stringNum[l],"......")
        if(stringNum[firstDigit_index]==stringNum[lastDigit_index]):           
            isPalindrome = True
        else:
            isPalindrome = False
            break
        firstDigit_index = firstDigit_index + 1
        lastDigit_index = lastDigit_index - 1

    if(isPalindrome):
        return number
    else:
        return 0

max = 0
startRange = 100
endRange = 999
for i in range(endRange*endRange,startRange*startRange,-1):
    factors = []
    result = isPaindrome(i)
    if(result!=0):
        for i in range(startRange,endRange+1):
            if(result%i==0):
                factors.append(i)
        if(len(factors)>1):
            sumFactor = factors[(len(factors))-1] + factors[(len(factors))-2]
            mul = factors[(len(factors))-1] * factors[(len(factors))-2]
            if(sumFactor>max and mul==result):
                max = sumFactor     

                print("Largest Palindrome made from product of two 3 digit numbers(",factors[(len(factors))-1],",",factors[(len(factors))-2] ,") is", result,".")

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

1 Ответ

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

Как я уже говорил, ваша функция isPalindrome буквально неверна, так как вы не меняете индексы. Я тоже немного изменил вашу, так что эту версию я анализирую. (Я только анализирую функцию isPalindrome, поскольку на самом деле я не мог понять, что делает основная функция), извините! 

def isPalindrome(n):
  num = str(n)
  head, tail = 0, len(num) - 1
  while tail > head:
    if num[head] != num[tail]: # Not symmetrical!! WARNING!
      return False
    head += 1 # move position
    tail -= 1 # move position
  return True

Этот код в среднем равен O(|n|) т.е. O (log N) где N это число. Это связано с тем, что в среднем сравнение if имеет 50% вероятности взлома (возвращение False) и 50% продолжения. Следовательно, ожидаемое количество сравнений будет | n | / 4, что равно O (| n |).

...