Algoritmalar bağlamında 'dizi erişimini' neler oluşturur?

Aşağıda, her dizenin tam olarak W karakterleri içerdiği bir dizi dizeyi sıralamak için Java'da bir ders kitabından alınan bir LSD Radix sıralama uygulaması bulunmaktadır.

Çalışma zamanı sırasında dizi erişimi sayısını saymak istiyorum. LSD sıralamasının n * c dizi erişimi gerektirdiğini ve buradaki n dizelerin sayısı ve c karakterlerin miktarını gerektirdiğini okudum. Her dizede. Bununla birlikte, aşağıdaki algoritma birkaç kez birden fazla diziye erişir. Bunların her birinde bir sayaç arttırırsam, nc önemli bir faktörle sonuçlanır.

Peki algoritmalar bağlamında tam olarak 'dizi erişimi' neyi oluşturur? Burada saymam gereken daha önemli kabul edilen sadece bir dizi erişim örneği var mı, yoksa bu örnek gerekenden daha fazla dizi erişimi kullanan verimsiz bir uygulama mı?

 public int lsdSort(String[] array, int W) {
  int access = 0;
 //Sort a[] on leading W characters.
  int N = array.length;
  String[] aux = new String[N];
  for (int d = W-1; d >= 0; d--)
  {//Sort by key-indexed counting on dth char.
    int[] count = new int[R+1];//Compute frequency counts.
    for (int i = 0; i < N; i++) {
        count[array[i].charAt(d) + 1]++;
    }
    for (int r = 0; r < R; r++) {
       //Transform counts to indices.
        count[r+1] += count[r];
    }
    for (int i = 0; i < N; i++) {
       //Distribute.
        aux[count[array[i].charAt(d)]++] = array[i];

    }  
    for (int i = 0; i < N; i++)//Copy back.
        array[i] = aux[i];
  }

  return access;
  }
4
Okunabilirliği artıran küçük düzenlemeler için Yuval'a teşekkürler!
katma yazar Lawyerson, kaynak

4 cevap

LSD sıralamasının, n dizelerinin sayısı ve c'nin her dizgideki karakterlerin sayısı olduğu nde c dizisinin erişimini gerektirmesi gerektiğini okudum.

O (nc) olduğunu okumadığınızdan emin misiniz? Bu kesinlikle aynı şey değil. big-O notasyonu var. Mesele, dizi erişiminin tam sayısını belirlemek değildir - nasıl büyüyeceği (veya nasıl büyüyeceğine dair sınırı ) n veya c artış. Bu durumda doğrusal olarak artar - n değerini 1000 kat artırırsanız, toplam maliyetin de yalnızca 1000 kat artmasını beklersiniz. 2 c) bunun yerine algoritma, 1.000.000 faktörü ile büyüyebilir. (Kesinlikle, herhangi bir O (nc) algoritmasının konuşması da O (n 2 c) çünkü sadece bir sınırdır, ama buna girmeyelim.

7
katma
@Parusa: Bu gerçekten ne anlama geldiği ve gerçekten mümkün olması mümkün. Büyük O bitinden daha az ilginç görünüyor.
katma yazar Jon Skeet, kaynak
Cevabınız için teşekkür ederim. Bu mantıklı görünüyor. Daha yeni algoritmalar çalışmaya başladım ve büyük O notalarına aşina oldum. Bununla birlikte, ders kitabım, beni şaşırtan bu uygulama örneğini sunmasına rağmen, Radix sıralamasının yalnızca c dizi erişimine tam olarak n dizilimine erişmesi gerektiği gibi görünüyor.
katma yazar Lawyerson, kaynak
@JonSkeet Kitap basitçe bana (kafa karıştırıcı bir şekilde de olsa) Radix sıralarının lineer zamanda sıralayabildiğini ve aslında bunu kesinlikle cn yapabileceğini, ancak gerçek verimi söyleyebileceğini söylemeye çalışıyor. uygulamaya bağlıdır. Zaman ayırdığın için teşekkürler!
katma yazar Lawyerson, kaynak
Gerçi, nc 'nin yapılabilmesi için hiçbir neden göremiyorum. Sadece c döngülere diziyi yineleyen ve değerleri yardımcı diziye yerleştiren döngüler yeterlidir. Pekala tamam, karakterleri geri yazmak zorunda olduğumuz için 2nc olduğunu, ancak farklı bir dizi ;-)
katma yazar Voo, kaynak

Birinci for döngüsü içindeki tüm dizi erişimleri, temel olarak birleştirilmiş dizi erişimleri olarak sayılır, bu yüzden c. N, bu birleşik dizinin kaç defa erişir yaptığıdır. Bu, gerçek erişim sayısını değil, fonksiyonun büyümesi hakkında yaklaşık bir fikir verir.

1
katma
public int lsdSort(String[] array, int W) {
  int access = 0;
 //Sort a[] on leading W characters.
  int N = array.length;
  String[] aux = new String[N];
  for (int d = W-1; d >= 0; d--)
  {//Sort by key-indexed counting on dth char.
    int[] count = new int[R+1];//Compute frequency counts.
    for (int i = 0; i < N; i++) {
        count[array[i].charAt(d) + 1]++;
        access++;
        access++;
    }
    for (int r = 0; r < R; r++) {
       //Transform counts to indices.
        count[r+1] += count[r];
        access++;
    }
    for (int i = 0; i < N; i++) {
       //Distribute.
        aux[count[array[i].charAt(d)]++] = array[i];
        access++; 
        access++;
        access++;   
    }  
    for (int i = 0; i < N; i++)//Copy back.
        array[i] = aux[i];
        access++;
        access++;
  }

  return access;

  }

Bir dizi 'erişim' bir okuma ya da bir yazıdır ...

1
katma
Örnek için +1. Aynı döngü içinde birkaç kez artış yapmayı düşünmemiştim. Cevabınız için teşekkür ederim!
katma yazar Lawyerson, kaynak

Big-O asimptotik gösterimlerinde erişim sayısı bir sabitle orantılıdır. Kodu analiz ettiğinizde, tüm sabitler atılır.

Radix Sıralamasında Büyük O O (cn) olur. Ancak, diziye kaç kez erişildiğini gerçekten saymak istiyorsanız, bu sayıyı k sabitiyle çarpmanız gerekir; burada k somut kodlanmış uygulamaya özeldir.

Örneğin, bu işlev O (n) 'dir, ancak dizinin erişilme sayısı 2n : değeri okumak için bir tane ve güncellemek için bir tane. 2 numarası atılır.

for (i=0; i
1
katma