Как мне продемонстрировать, что следующий алгоритм имеет O (nlogn) временную сложность - PullRequest
Новая
       2

Как мне продемонстрировать, что следующий алгоритм имеет O (nlogn) временную сложность

0 голосов
/ 21 октября 2019

Это алгоритм, который находит минимальное число нисходящих строк и сами строки массива в O (nlogn) временной сложности. Другая часть упражнения заключается в использовании этих убывающих строк для реализации сортировки терпения, которая также должна быть O (nlogn) (то есть из части c = 1). Чего я не понимаю, так это того, откуда берется часть logn в обоих случаях. 

#include <iostream>
#include <fstream>
#include <list>
using namespace std;

ifstream f("data.in");

int main()
{
    int n, v[100];
    f >> n;
    for (int i = 0; i < n; i++)
        f >> v[i];
    list<int> aux;
    aux.push_back(v[0]);
    list<list<int> > rows;
    rows.push_back(aux);
    for (int i = 1; i < n; i++)
    {
        int selected = 0;
        for (list<list<int> >::iterator it = rows.begin(); it != rows.end(); it++)
        {
            if (it->back() > v[i])
            {
                it->push_back(v[i]);
                selected = 1;
                break;
            }
        }
        if (!selected)
        {
            list<int> aux;
            aux.push_back(v[i]);
            rows.push_back(aux);
        }

    }
    for (list<list<int> >::iterator it = rows.begin(); it != rows.end(); it++)
    {
        for (list<int>:: iterator it2 = it->begin(); it2 != it->end(); it2++)
            cout << *it2 << " ";
        cout << endl;
    }

    int c = 1;
    if (c == 1)
    {
        int s[100];
        for (int i = 0; i < n; i++)
        {
            list<list<int> >::iterator it = rows.begin();
            int minim = it->back();
            it++;
            while (it != rows.end())
            {
                if (!it->empty())
                    if (it->back() < minim)
                        minim = it->back();
                it++;
            }
            it = rows.begin();
            while (it != rows.end())
            {
                    if (it->back() == minim)
                    {
                        it->pop_back();
                        if (it->empty())
                            rows.erase(it);
                        break;
                    }
                it++;
            }
            s[i] = minim;
        }
        for (int i = 0; i < n; i++)
            cout << s[i] << " ";

    }

}

1 Ответ

0 голосов
/ 21 октября 2019

Ваши внешние циклы обрабатывают каждый фрагмент входных данных, поэтому рост является линейным, например, O (n). Ваши внутренние циклы обрабатывают только меньшее подмножество полных входных данных, и рост является логарифмическим, например O (log n). Следовательно, рост является линейным, например, O (nlogn). Если внутренний цикл обрабатывает каждый фрагмент входных данных, рост будет квадратичным, например O (n ^ 2)

Хорошее объяснение можно найти здесь:

Что означает O(журнал n) означает точно?

РЕДАКТИРОВАТЬ: Моя ошибка. Я согласен с комментариями под оригинальным постом, что рост программы, кажется, O (n ^ 2). Я был немного быстр в поворотах. При быстром взгляде мне сначала показалось, что внутренние циклы были выполнены log n раз. Но, похоже, это не относится к внутренним циклам во вторых n итерациях. Однако, насколько я понимаю, первая внутренняя петля кажется мне выполненной log n раз (так что порядок сортировки строк - O (nlogn)), но, возможно, я ошибаюсь.

...