Soru: üç diziler ve O (*N N) | Netgez.com
SORU
21 EKÄ°M 2010, PERÅžEMBE

Soru: üç diziler ve O (*N N)

Biz varsayalımüçuzunluğu dizileriNyazın rasgele sayılar long içeren. Sonra bir numara verilirM(aynı türden) ve misyonumuz üç sayı seçmekBir,BveCher diziden bir (diğer bir deyişleBirgerekirilk diziden, toplanırBgelen ikinci veCüçüncü) toplamıC = A B M.

Soru:üç sayı seç ve zaman karmaşıklığı ile sonuna kadarO(N2)?

Örnek:

Diziler

1) 6 5 8 3 9 2
2) 1 9 0 4 6 4
3) 7 8 1 5 4 3

VeMverildi19. O zaman bizim seçim olacaktır8ilk gelen,4ikinci ve7üçüncü.

CEVAP
21 EKÄ°M 2010, PERÅžEMBE

Bu O(1) Uzay ve O(N . yapılabilir ^sup>2) zaman.

İlk sağlar basit bir sorunu çözmek:
İki dizi verilen A B bunların toplamı 6 ** verilen sayıya eşit olan her bir öğe seçin.

O aldığı her iki dizi(NlogN) tür.
i A j Bsonuna işaret dizinin başlangıcına işaret eden işaretçiler i j al.
Toplamı A[i] B[j] K ile karşılaştırın

  • bulduk A[i] B[j] == K çifti A[i] B[j]
  • eÄŸer A[i] B[j] < K, gerekirse toplam artış, artış i.
  • eÄŸer A[i] B[j] > K, gerekirse toplam azalma, azaltma j.

Sıralama sonra çifti bulmak için bu işlem O(N) alır.

Şimdi asıl sorun atalım. Üçüncü bir dizi şimdi C çağrı var.

Yani algoritma ..

foreach element x in C
  find a pair A[i], B[j] from A and B such that A[i]   B[j] = K - x
end for

Dış döngü(N) işlemi, tüm algoritma O hale yaptığımız her çalışma için N kat ve(N çalıştırır2).

Bunu PaylaÅŸ:
  • Google+
  • E-Posta
Etiketler:
DizilerArraysAlgoritmaAlgorithm

AYNI ETÄ°KETTEKÄ° VÄ°DEOLAR

YORUMLAR

SPONSOR VÄ°DEO

Rastgele Yazarlar

  • Kassem G

    Kassem G

    25 EKÄ°M 2006
  • Peyton

    Peyton

    28 Aralık 2008
  • Rozetked | Обзоры

    Rozetked | Ð

    5 AÄžUSTOS 2011

Ä°LGÄ°LÄ° SORU / CEVAPLAR

Ä°LGÄ°LÄ° BAÄžLANTILAR