Я правильно рассчитываю сравнения массивов в этом скрипте? - PullRequest
Новая
       9

Я правильно рассчитываю сравнения массивов в этом скрипте?

0 голосов
/ 26 января 2019

У меня есть этот скрипт ниже, который находит самые маленькие и самые большие значения в массиве целых чисел.Цель состоит в том, чтобы выполнить эту задачу менее чем за 1,5 x N сравнений, где N - длина входного массива, n_list .Я хочу задать пару вопросов.

1: (внутри цикла для ) сравнивает переменные наименьший или наибольший с n , рассматриваемый как массивсравнение?В приведенном ниже сценарии я считаю его одним.Если это так, то почему это так?Определение, которое мне удалось найти, говорит о том, что сравнение массивов проводится между двумя массивами, и это не совсем то, что я делаю, IMO.

2: Если я не считаю правильно, что я делаю не так?

3: Как лучше подходить к этой проблеме?

Большое спасибо, надеюсьу вас хороший день / ночь:) 

 def findExtremes(n_list):

   smallest = n_list[0]
   largest = n_list[0]
   counter = 2 # See above

   for n in n_list:
      if n > largest:
         largest = n
         counter += 1
         continue
      elif n < smallest:
         smallest = n
         counter += 1
         continue
      else:
         counter += 1
         continue

   return(counter)

1 Ответ

0 голосов
/ 26 января 2019

Вы считаете только успешные сравнения.

Когда первый if успешен, вы сделали одно сравнение, и вы правильно делаете counter += 1.

Но если выпопадайте в elif, вы сделали два сравнения: n > largest и n < largest, поэтому вам нужно выполнить counter += 2.

И если это сравнение не удастся, выВы все еще сделали два сравнения, поэтому вам также нужно выполнить counter += 2 в блоке else.

Вам не нужно инициализировать counter = 2 в начале, вы должны установить его на0.Вы посчитаете два сравнения с первым элементом списка в цикле.

На самом деле, вы можете просто пропустить эти элементы, так как результат известен.Вы можете сделать: 

for n in n_list[1:]:

, чтобы пропустить их.Если вы должны считать эти ненужные сравнения, то имеет смысл инициализировать counter = 2.

Ваш вопрос о «сравнении массивов», похоже, вообще не актуален.В этой задаче нет ничего общего со сравнением массивов, вы просто сравниваете элементы массива с другими элементами этого же массива.

Ваш алгоритм выполняет от N + 1 до 2 * N сравнений.В лучшем случае массив сортируется от наименьшего к наибольшему - тест, который обновляет largest, успешно выполняется для каждого элемента, поэтому ему никогда не нужно обновлять smallest.Наихудший случай - когда он отсортирован в обратном порядке или все числа одинаковы: все тесты largest не пройдены, поэтому необходимо проверить каждый элемент, чтобы узнать, является ли он новым smallest.В среднем со случайными данными это имеет тенденцию быть близко к худшему случаю, около 1,95 * N.

...