Алгоритмдер контексіндегі «массивке қол жеткізу» дегеніміз не?

Төменде әр жолда W таңбалары бар жолдардың массивін сұрыптау үшін оқулықта Java-дегі LSD Radix сұрыптауы берілген.

Орындау уақытында массивтердің санын санауды қалаймын. LSD сұрыптауының n * c массивіне кіруін талап ететінін оқыдым, онда n - бұл жолдардың саны және c әрбір жолда. Алайда, төмендегі алгоритм бірнеше массивке бірнеше рет кіреді. Есептегіштің әрқайсысына арттырсам, мен nc маңызды факторымен аяқталады.

Сонымен, алгоритмдер контексінде дәл «массивтік қатынау» деген не? Массивге қатынаудың тек бір данасы бар, ол осы жерде санауға болымды деп есептеледі ме, әлде бұл мысал қажет болғанға қарағанда көп жиым қатынасын пайдаланатын тиімді емес іске асыру?

 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
Yuval-ға арқасында кішкентай түзетулерге, ол оқылуды жақсартады!
қосылды автор Lawyerson, көзі

4 жауаптар

LSD сұрыптауының n уақыт c массивіне кіруін талап ететінін оқыдым, мұнда n - әр жолдағы таңбалардың саны және с саны.

O (nc) дегенді оқымағаныңызға сенімдісіз бе? Бұл мүлдем бірдей емес. Бұл үлкен-O белгісі . Массивге қатынаудың нақты санын анықтау емес - бұл ол қалай өсетіні туралы айту (яғни, ол n ) ретінде немесе одан қалай өсетінін шегі c ұлғайту. Бұл жағдайда, егер ол 1000 коэффициентімен n көбейтілсе, онда сіз жалпы 1000-ға дейін өседі деп күтуге болады ... егер бұл O (n 2 c) алгоритм орнына, ол 1,000,000 есе өседі. (Әрине, кез келген O (nc) алгоритмі сондай-ақ O (n 2 c).

7
қосылды
@Parusa: Мүмкін, бұл шын мәнінде нені білдіреді, және шын мәнінде мүмкін. қызықты қарағанда үлкен-O битінен аз.
қосылды автор Jon Skeet, көзі
Жауабыңызға рахмет. Бұл мағынасы бар сияқты. Мен жақында ғана алгоритмдерді зерттей бастадым және үлкен-O белгілерімен таныспын. Менің оқулықта, бірақ, Radix сұрыптауы мені шатастыратын осы іске қосу үлгісіне қарамастан, c әрбір жолға n үшін массивге қатынау қажет болған сияқты көрінеді.
қосылды автор Lawyerson, көзі
@JonSkeet Менің ойымша, кiтапша Radix сұрыптайды желiлiк уақыт бойынша сұрыптау мүмкiндiгiн (iс жүзiндегi жағдайда да) айтқысы келедi және бұл шынымен мүмкін дегендi қатаң түрде жасайды, жүзеге асыруға байланысты. Сіздің уақытыңыз үшін рахмет!
қосылды автор Lawyerson, көзі
Мен nc дегенді не істеуге болмайтынын білмеймін. Сізге c керек, алаптары арқылы қайталап, мәндерді көмекші массивке қою. Жақсы тәртіппен 2nc деп айтуға болады, өйткені біз кейіпкерлерді қайтадан жазуымыз керек, бірақ әр түрлі массив ;-)
қосылды автор Voo, көзі

Барлық массивтің алғашқы ішінде цикл ішіндегі қатынастары, әдетте, массив қатынасының жиынтық саны ретінде есептеледі, сондықтан сіздің c. N - бұл біріктірілген массивтерге қатынауды қанша рет жасайсыз. Бұл функцияның нақты өсу санына емес, функцияның өсуі туралы болжамды береді.

1
қосылды
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;

  }

массивтің «қолжетімділігі» - бұл оқу немесе жазу ...

1
қосылды
+1 мысал үшін. Мен сол цикл ішінде бірнеше рет артуды қарастырған жоқпын. Жауабыңызға рахмет!
қосылды автор Lawyerson, көзі

Big-O асимптотикалық белгілерінде қатынау саны тұрақты мәнге пропорционалды. Кодты талдағанда, барлық тұрақты мәндер жойылады.

Radix жағдайда Үлкен O-ні сұрыптау O (cn) . Бірақ егер массив қанша рет қолжетімді екенін санап алғыңыз келсе, бұл кодты k нақты кодын енгізуге нақты болатын k тұрақты коды үшін көбейту керек.

Мысалы, бұл функция O (n) болып табылады, бірақ массивтің қанша рет қатынайтыны - 2n : біреуін оқу үшін және біреуін жаңартуға арналған. 2 нөмірі жойылады.

for (i=0; i
1
қосылды