Какой из двух алгоритмов для определения массива суффиксов быстрее и почему?

Question

Я новичок в сложности алгоритма и поэтому не могу понять сложности следующих двух алгоритмов. Оба обнаруживают массив суффиксов для данной строки. Первая создана мной одна и вторая, которую я нашел в Интернете. Я хочу знать, кто из них быстрее и почему?

ПЕРВЫЙ АЛГОРИТМ

#include<iostream> 
#include<string> 
using namespace std; 
struct suffix{ 
    string str; 
    int pos; 
}; 
int main() 
{ 
    string input; 
    suffix arr[100]; 
    getline(cin,input,'\n'); 
    for(int i=0;i<input.length();i++) 
    { 
     for(int j=i;j<input.length();j++) 
     { 
      arr[i].str+=input[j]; 
     } 
      arr[i].pos=i; 

     for(int j=0;j<i;j++) 
     { 
      if(arr[i].str.compare(arr[j].str)<0)  
      { 
       string temp=arr[i].str; 
       arr[i].str=arr[j].str; 
       arr[j].str=temp; 
       int tem=arr[i].pos; 
       arr[i].pos=arr[j].pos; 
       arr[j].pos=tem; 
       break; 
      } 

     } 
    } 
    for(int i=0;i<input.length();i++) 
     cout<<arr[i].pos<<","; 
    return 0; 
} 

ВТОРОЙ АЛГОРИТМ

#include bits/stdc++.h 
using namespace std; 

// suffixRank is table hold the rank of each string on each iteration 
// suffixRank[i][j] denotes rank of jth suffix at ith iteration 

int suffixRank[20][int(1E6)]; 

// Example "abaab" 
// Suffix Array for this (2, 3, 0, 4, 1) 
// Create a tuple to store rank for each suffix 

struct myTuple { 
    int originalIndex; // stores original index of suffix 
    int firstHalf;  // store rank for first half of suffix 
    int secondHalf;  // store rank for second half of suffix 
}; 


// function to compare two suffix in O(1) 
// first it checks whether first half chars of 'a' are equal to first half chars of b 
// if they compare second half 
// else compare decide on rank of first half 

int cmp(myTuple a, myTuple b) { 
    if(a.firstHalf == b.firstHalf) return a.secondHalf < b.secondHalf; 
    else return a.firstHalf < b.firstHalf; 
} 

int main() { 

    // Take input string 
    // initialize size of string as N 

    string s; cin >> s; 
    int N = s.size(); 

    // Initialize suffix ranking on the basis of only single character 
    // for single character ranks will be 'a' = 0, 'b' = 1, 'c' = 2 ... 'z' = 25 

    for(int i = 0; i < N; ++i) 
     suffixRank[0][i] = s[i] - 'a'; 

    // Create a tuple array for each suffix 

    myTuple L[N]; 

    // Iterate log(n) times i.e. till when all the suffixes are sorted 
    // 'stp' keeps the track of number of iteration 
    // 'cnt' store length of suffix which is going to be compared 

    // On each iteration we initialize tuple for each suffix array 
    // with values computed from previous iteration 

    for(int cnt = 1, stp = 1; cnt < N; cnt *= 2, ++stp) { 

     for(int i = 0; i < N; ++i) { 
      L[i].firstHalf = suffixRank[stp - 1][i]; 
      L[i].secondHalf = i + cnt < N ? suffixRank[stp - 1][i + cnt] : -1; 
      L[i].originalIndex = i; 
     } 

     // On the basis of tuples obtained sort the tuple array 

     sort(L, L + N, cmp); 

     // Initialize rank for rank 0 suffix after sorting to its original index 
     // in suffixRank array 

     suffixRank[stp][L[0].originalIndex] = 0; 

     for(int i = 1, currRank = 0; i < N; ++i) { 

      // compare ith ranked suffix (after sorting) to (i - 1)th ranked suffix 
      // if they are equal till now assign same rank to ith as that of (i - 1)th 
      // else rank for ith will be currRank (i.e. rank of (i - 1)th) plus 1, i.e (currRank + 1) 

      if(L[i - 1].firstHalf != L[i].firstHalf || L[i - 1].secondHalf != L[i].secondHalf) 
       ++currRank; 

      suffixRank[stp][L[i].originalIndex] = currRank; 
     } 

    } 

    // Print suffix array 

    for(int i = 0; i < N; ++i) cout << L[i].originalIndex << endl; 

    return 0; 
} 

Answer 1

Чтобы определить, какой из них работает быстрее для данного N, вам нужно будет запустить их обоих и посмотреть. Чтобы определить, какой из них будет лучше масштабироваться, вы можете просто просмотреть свои петли.

В своем первом алгоритме, у вас есть вложенные циклы, которые оба идут от 0 к input.size() с шагом 1, который O(N^2) (если input.size() является 1, обе петли выполняются один раз в общей сложности один проход, если input.size() является 2, внешний цикл выполняется дважды, а внутренний цикл выполняется дважды для каждого цикла внешнего цикла для всего 4 итераций и т. д.).

Второй алгоритм, однако, имеет внешний цикл, который идет от 0 до N и умножается на 2 на каждой итерации. Это растет как log(N), а не N. Таким образом, это O(N*log(N)), что меньше O(N^2) и, скорее всего, будет лучше масштабироваться.