Des carrés d'une matrice triée, pourquoi la méthode triée () est plus rapide que O (n) la méthode?

La Time LeetCode Rapports est la somme sur tous les cas de test que votre solution a été testée. Ceci est très peu fiable comme une mesure d'efficacité algorithmique, car

• La plupart des cas de test sont sur de petites entrées, li>
• L'heure limitée prise par le juge lui-même est substantielle et assez variable, de sorte que même des différences modérées entre deux mesures pourraient dépendre de la variation aléatoire de cette surcharge. Li> ul>

  voir Cette réponse pour plus de discussion. p>

  ---

  donc si si Nous voulons comparer les performances des deux algorithmes, il vaut mieux le faire nous-mêmes. J'ai fait; Voici mon temps pour les listes de taille pouvant atteindre 5 000 personnes (moyenne sur 1 000 points chacune): p>

  p>

  Voici mon temps pour les listes de listes de taille jusqu'à 1 000 000 (pas de moyenne de moyenne): p>

  p>

  Comme vous pouvez le constater, en utilisant trié code> est toujours plus rapide Pour les petites et grandes entrées, la comparaison de Leetcode est donc correcte cette fois-ci (bien que peut-être juste par coïncidence quand même!). Votre solution est en effet linéaire et ces résultats sont compatibles avec cela. Mais la solution utilisant trié code> semble également prendre du temps linéaire, et la réponse de Wasp Overflow explique pourquoi elle devrait. P>

  Mon code de synchronisation est ci-dessous. Les temps ont été mesurés à l'aide de Python 3.5.2 et je reçois des résultats similaires avec Python 3.8.1. P>

  def linear(A):
      start = 0
      end = len(A)-1
      B = []
      while start <= end:
          if abs(A[start]) >= abs(A[end]):
              B.append(A[start] * A[start])
              start += 1
          else:
              B.append(A[end] * A[end])
              end -= 1
      B.reverse()
      return B
  
  def using_sorted(A):
      return sorted(x*x for x in A)
  
  from timeit import timeit
  from random import randint
  
  print('n', 'linear', 'using sorted', sep='\t')
  for n in range(10000, 1000001, 10000):
      data = sorted(randint(-10*n, 10*n) for i in range(n))
      t1 = timeit(lambda: linear(data), number=1)
      t2 = timeit(lambda: using_sorted(data), number=1)
      print(n, t1, t2, sep='\t')