Uzun bölümün karmaşıklığı nedir?

Question

Dersimde profesörüm çeşitli aritmetik işlemlerin büyük O zamanlarını açıklıyordu. Bize uzun bölümün O (n^2) civarında olduğunu söyledi. Çevrimiçine baktığımızda bunun doğru olduğunu düşünüyoruz, ama neden?

Uzun bölümün neden O (n^2) saatte olduğuna dair ayrıntıya giren var mı?

Answer 1

Bu bit sayısı m tarafından n bölmek anlamına gelir Eğer bölüyorlar sayılar, sen O((log max(m,n))^2) zamana ihtiyacı yılında kuadratik bu. Bunun nedeni, her bir çıkarma işleminin O(log max(m, n)) zamanını almasıdır.

Açıklama var here on StackOverflow.