Быстрая сортировка - Пространственная сложность - Почему это O (logN), а не O (N)?

Question

Итак, в быстрой сортировке говорят, что сложность пространства равна O (log N), но вот то, что я подумал. Поскольку logN возникает из стековых вызовов, всегда можно выбрать наихудший стержень, ведущий к вызовам O (N), а не к вызовам O (logN)? Разве это не должно быть O (N)?

Answer 1

Этот пример java ограничивает пространство стека до O (log (n)), используя только рекурсию для меньшей части, а затем возвращая цикл для обработки большей части. В худшем случае сложность времени все еще равна O (n ^ 2).

public static void qsort(long[] a, int lo, int hi)
{
    while(lo < hi){
        int  md = lo+(hi-lo)/2;
        int  ll = lo-1;
        int  hh = hi+1;
        long p = a[md];
        long t;
        while(true){
            while(a[++ll] < p);
            while(a[--hh] > p);
            if(ll >= hh)
                break;
            t     = a[ll];
            a[ll] = a[hh];
            a[hh] = t;
        }
        ll = hh++;
        if((ll - lo) <= (hi - hh)){
            qsort(a, lo, ll);
            lo = hh;
        } else {
            qsort(a, hh, hi);
            hi = ll;
        }
    }
}