Какова временная сложность этого алгоритма. Могу ли я сделать это быстрее? - PullRequest
Новая
       42

Какова временная сложность этого алгоритма. Могу ли я сделать это быстрее?

0 голосов
/ 03 декабря 2018

этот алгоритм находит наиболее перекрывающиеся действия (полосы) в определенных интервалах, которые начинаются в arrl и заканчиваются в depr. Я использовал быструю сортировку для сложности времени O (nlogn) и затем цикл while с O (n) для подсчета числаконфликтующие действия в этих интервалах 1. Так это как O (nlogn) + O (n) сложность времени?2.Могу ли я сделать это еще быстрее в O (N)?3. Наконец, теоретически возможно ли использовать Timsort для O (n) временной сложности?

Код, написанный на C, предназначен для 15 действий, но, скажем, он обобщенный и с несортированными arrl и depr

РЕДАКТИРОВАТЬ: Результатом является большинство действий в течение 1 часа 

void findMaxBands(int n,int arr1[n],int depr[n]);
void quickSort(int a[],int l,int h);
int partition(int a[],int l,int h);

int main(){
    int arrl[15] = {18,18,19,19,19,19,20,20,20,20,21,22,22,22,23};
    int depr[15] = {19,21,20,21,22,23,21,22,22,23,23,23,24,24,24};
    int n = 15;
    findMaxBands(n,arrl,depr);
    return 0;
}

void findMaxBands(int n,int arrl[n],int depr[n]){
    quickSort(arrl,0,15);
    quickSort(depr,0,15);

    int guestsIn = 1,maxGuests = 1,time = arrl[0];
    int i = 1, j = 0;

    while (i < n && j < n){
        if (arrl[i] <= depr[j]){
            guestsIn++;
            if (guestsIn > maxGuests){
                maxGuests = guestsIn;
                time = arrl[i];
            }
            i++;
        }
        else{
            guestsIn--;
            j++;
        }
    }
    printf("Maximum Number of Bands : %d at time %d-%d",maxGuests,time-1,time);
}

void quickSort(int a[],int l,int h){
    int j;
    if(l<h){
        j=partition(a,l,h);
        quickSort(a,l,j-1);
        quickSort(a,j+1,h);
    }
}

int partition(int a[],int l,int h){
    int v,i,j,temp;
    v=a[l];
    i=l;
    j=h+1;

    do{
        do{
            i++;
        }while(a[i]<v&&i<=h);
        do{
            j--;
        }while(v<a[j]);
        if(i<j){
            temp=a[i];
            a[i]=a[j];
            a[j]=temp;
        }
    }while(i<j);
    a[l]=a[j];
    a[j]=v;
    return(j);
}

1 Ответ

0 голосов
/ 03 декабря 2018

1.Так как O (nlogn) + O (n) сложность во времени?

O (n log (n)) + O (n) = O (nlog (n))

Ref.например. Большой O при сложении различных подпрограмм для более подробной информации.

2.Могу ли я сделать это еще быстрее при O (n)?

3.Настоящее время,теоретически, возможно ли использовать Timsort для O (n) временной сложности?

Алгоритм сортировки общего назначения (сравнения) может иметь наилучшую сложность O (n), но среднее / худшееcase будет иметь сложность O (n log (n)) в лучшем случае.Вы можете найти обзор нескольких алгоритмов сортировки здесь с их сложностями.

...