Теоретическая часть


if (f == tail)//1 { delete



страница3/4
Дата12.08.2022
Размер1,04 Mb.
#188273
1   2   3   4
Связанные:
kursovaya

if (f == tail)//1

  • {

      1. delete f;

      2. head = tail = NULL;//2

      3. nop+=3;

  • }

  • else

  • {

    1. nop++;

    2. while (f->next != tail)//1

      1. {

      2. f = f->next;//1

      3. nop+=2;

      4. }

    3. delete tail;

    4. tail = f;

    5. tail->next = NULL;

    6. nop+=2;

  • }

  • size--;

  • nop++;

    1. };

    В строке b—1 операция(создание элемента), в строке 2—1 оп.(сравнение). Рассмотрим ветки if и else в строке 2 по отдельности.
    1. if) В строке 3.ii – 2 операции (двойное присваивание)
    2. else) В строке 6b – 1 операция(сравнение). В строке 6.b цикл выполнится n-2 раза. В цикле будет происходить сравнение(6b) – 1 операция и присваивание(6bii) – 1 операция. Следовательно общее количество операций цикла равно (n-2)2. В строке 6d –присваивание(1 опер.), в строке 6e –присваивание(1 опер.). Итого: 1+2(n-2)+2. Следовательно, в ветке else операций больше, при расчёте формулы учитываем это.
    В строке 8 1 операция – уменьшение на 1.
    Итого: F(n)= 1+1+1+2(n-2)+2+1=2n+2
    Листинг программы.
    #include
    #include
    //#include
    #include
    #include
    #include
    using namespace std;
    unsigned long long int nop = 0;
    class element{
    public:
    int value;
    element *next;
    element *prev;
    };


    class Deque{
    public:
    int size;
    element* head;
    element* tail;

    Deque(){


    size=0;
    head=0;
    tail=0;
    nop++;
    }


    void AddL(int el)//8
    {
    nop++;//ïðîâåðêà óñëîâèÿ
    if (size==0)//1
    {
    element *a=new element;//1
    a->next=0;//1
    a->prev=0;//1
    a->value=el;//1
    head=a;//1
    size++;//1
    nop+=6;
    }
    else{
    element *a = new element;//1
    a->next = head;//1
    a->prev = 0;//1
    a->value=el;//1
    head->prev=a;//1
    head=a;//1
    size++;//1
    nop+=7;
    }
    };
    void AddR(int el)//6
    {
    nop++;
    if (head==0)//1
    {
    head = new element;//1
    tail=head;//1
    head->value=el;//1
    head->next=0;//1
    nop+=4;
    }
    else{
    tail->next=new element;//1
    tail->next->value=el;//1
    tail->next->next=0;//1
    tail=tail->next;//1
    nop+=4;
    }
    size++;
    nop++;
    };
    void DeleteR()//1+1+1+2(n-2)+2+1=2n+2
    {
    nop++;
    element *f = head;//1
    nop++;
    if (f == tail)//1
    {
    delete f;
    head = tail = NULL;//2
    nop+=3;
    }
    else
    {
    nop++;
    while (f->next != tail)//1
    {
    f = f->next;//1
    nop+=2;
    }
    delete tail;
    tail = f;
    tail->next = NULL;
    nop+=2;
    }
    size--;
    nop++;
    };

    void DeleteL()//7


    {
    nop++;
    if (getQueueSize()==0)//1
    return;
    else
    {nop++;
    if(head==tail)//1
    {
    head=0;//1
    nop++;
    }
    else{
    element *f;//1
    f=head;//1
    head=f->next;//1
    delete f;
    nop+=3;
    }
    }
    size--;
    nop++;
    };

    int getQueueSize()


    {
    return size;
    };

    bool isEmpty()//1


    {
    nop++;
    if (getQueueSize()==0)//1
    return 1;

    return 0;


    };
    int Value()//2
    {
    element* f3;//1
    f3 = head;//1
    nop+=2;
    return f3->value;
    };

    int ValueR()//2


    {
    element* f3;
    f3 = tail;
    nop+=2;
    return f3->value;
    };
    };


    void Prohod(Deque &q)//17
    {
    int temp;//1
    temp = q.Value();//1+2
    nop+=2;
    q.DeleteL();//7
    q.AddR(temp);//6
    temp=0;//1
    nop++;
    }


    void Show(Deque &q){
    cout << "Âàø ìàññèâ - " << endl;
    cout << endl;
    for (int i=0; i cout << q.Value() << " ";
    Prohod(q);
    }
    cout << endl;
    cout << endl;
    }
    void set(Deque &q, int n, int ne)//20n-2
    {

    for (int i=0; i {
    nop+=3;
    if (i==n)
    {
    q.DeleteL();//7
    q.AddR(ne);//6
    }
    else{
    Prohod(q);//17
    }
    }
    nop+=2;
    }


    int get(Deque &q, int n)//20n-20+19+1+2=20n+2
    {

    int res=0;//1


    nop++;
    for (int i=0; i {
    nop+=3;
    if (i==n)//1
    {
    nop++;
    res=q.Value();//1+2
    q.DeleteL();//7
    q.AddR(res);//6
    }
    else{
    Prohod(q);//17
    }
    }
    nop+=2;
    return res;
    }
    void SortirovkaVstavkoy(Deque &q, int n){
    int temp, // âðåìåííàÿ ïåðåìåííàÿ äëÿ õðàíåíèÿ çíà÷åíèÿ ýëåìåíòà ñîðòèðóåìîãî ìàññèâà
    item; // èíäåêñ ïðåäûäóùåãî ýëåìåíòà
    nop+=2;
    for (int i= 0; i < n; i++)
    {
    temp = get(q , i); // èíèöèàëèçèðóåì âðåìåííóþ ïåðåìåííóþ òåêóùèì çíà÷åíèåì ýëåìåíòà ìàññèâà
    //1
    item = i-1; // çàïîìèíàåì èíäåêñ ïðåäûäóùåãî ýëåìåíòà ìàññèâà
    //2
    nop+=3;
    nop+=2;
    while(item >= 0 && get( q , item ) > temp) //2
    // ïîêà èíäåêñ íå ðàâåí 0 è ïðåäûäóùèé ýëåìåíò ìàññèâà áîëüøå òåêóùåãî
    {
    set(q , item+1 , get( q , item )); //1
    // ïåðåñòàíîâêà ýëåìåíòîâ ìàññèâà
    item--;//1
    nop+=4;
    }
    set(q , item+1 , temp);
    nop++;
    }
    }


    void RandomnoeZapolnenie(Deque &q, int n){
    for (int i=0; i q.AddR(-100+rand()%200);
    }


    void UdalenieVsego(Deque &q){
    int n=q.getQueueSize();
    for (int i=0; i q.DeleteL();
    }
    /**/
    void menu(){
    cout << "0 - çàïîëíèòü ñëó÷àéíûìè ýëåìåíòàìè" << endl;
    cout << "1 - äîáàâèòü ýëåìåíò ñëåâà" << endl;
    cout << "2 - äîáàâèòü ýëåìåíò ñïðàâà" << endl;
    cout << "3 - óäàëèòü ýëåìåíò ñëåâà" << endl;
    cout << "4 - óäàëèòü ýëåìåíò ñïðàâà" << endl;
    cout << "5 - âûâåñòè ïåðâûé ýëåìåíò íà óäàëåíèå ñëåâà" << endl;
    cout << "6 - âûâåñòè ïåðâûé ýëåìåíò íà óäàëåíèå ñïðàâà" << endl;
    cout << "7 - ñîðòèðîâêà" << endl;
    cout << "8 - î÷èñòèòü âñå" << endl;
    cout << "9 - âûõîä" << endl;
    };
    int main(){
    srand(time(NULL));
    setlocale(LC_ALL, "Rus");
    int h=0;
    Deque q;

    while (h!=9){


    menu();

    do{


    cin >> h;
    if (h<-1 or h>9)
    cout << "îøèáêà" << endl;
    }
    while (h<0 and h>9);

    switch (h){


    case 0:
    int nu;
    cout << "�'êîëüêî ýëåìåíòîâ ââåñòè?" << endl;
    cin >> nu;
    if (q.isEmpty()==0){
    cout << "Î÷åðåäü óæå ÷åì-òî çàïîëíåíà" << endl;
    system("pause");
    }
    else
    RandomnoeZapolnenie(q, nu);
    system("CLS");
    Show(q);
    break;
    case 1:
    int el;
    cout << "Ââåäèòå ýëåìåíò" << endl;
    cin >> el;
    q.AddL(el);
    system("CLS");
    Show(q);
    break;
    case 2:
    int el1;
    cout << "Ââåäèòå ýëåìåíò" << endl;
    cin >> el1;
    q.AddR(el1);
    system("CLS");
    Show(q);
    break;
    case 3:
    q.DeleteL();
    system("CLS");
    Show(q);
    break;
    case 4:
    q.DeleteR();
    system("CLS");
    Show(q);
    break;
    case 5:
    cout << endl;
    cout << "Ïåðâûé ýëåìåíò íà óäàëåíèå - " < cout << endl;
    system("pause");
    system("CLS");
    Show(q);
    break;
    case 6:
    cout << endl;
    cout << "Ïåðâûé ýëåìåíò íà óäàëåíèå - " < cout << endl;
    system("pause");
    system("CLS");
    Show(q);
    break;
    case 7:
    SortirovkaVstavkoy(q, q.getQueueSize());
    system("CLS");
    Show(q);
    break;
    case 8:
    UdalenieVsego(q);
    system("CLS");
    Show(q);
    break;
    }
    }
    return 1;
    }

    /*int main()


    {
    srand(time(NULL));
    setlocale(LC_ALL, "Rus");
    int h=0;
    Deque q;
    ofstream fl("andr.txt");
    for (int i=1;i<2001;i++)
    {
    //fl<<(rand());
    //fl<<-i;
    fl< //fl<<1;
    fl<<" ";
    }
    fl.close();
    int i, N,b;
    for (N=200;N<2001;N+=200)
    {
    ifstream f("andr.txt");
    for (i=1;i {
    if(f >> b)
    {//cout << b << std::endl;
    q.AddR(b);
    }
    }
    int t1,t2;

    nop=0;
    t1=GetTickCount();
    SortirovkaVstavkoy(q, q.getQueueSize());
    //cout< t2=GetTickCount();
    cout< cout< UdalenieVsego(q);
    f.close();
    }
    }
    */

    Расчёты трудоёмкости и выводы функции роста.
    Сложность алгоритма измеряется числом сравнений и равна O(n^2).
    Наилучший случай - когда исходный список уже отсортирован.
    Тогда на i-ом проходе вставка производится в точке A[i],
    а общее число сравнений равно n-1, т.е. сложность составляет O(n).
    Наихудший случай возникает, когда список отсортирован по убыванию.
    Тогда каждая вставка происходит в точке A[0] и требует i сравнений.
    Подсчёт операций в сортировке.
    F(n)=2(int temp,item;)+(цикл for (int i= 0; i < n; i++) )n * ( (объявление переменной temp) 1 + (get(q,i);) (20n+2) + (item=i-1;) 2+( while(item >= 0 && get( q , item ) > temp)) (20n+2+2) + (set(q , item+1 , temp);) (20n-2+1))+ (цикл while(item >= 0 && get( q , item ) > temp) ) n-1i=0 i*( (проверки и get в цикле) (2+20n+2) + (set(q , item+1 , get( q , item ));) (20n-2+1+20n+2) +(item--;) 1)=
    =2+n(1+20n+2+2+2+20n+2+1+20n-2)+∑n-1i=0 i*(2+20n+2+20n+2+20n-2+2)=
    =2+n(60n+8)+(n^2-n)(6+60n)/2=2+60n^2+8n+3n^2+30n^3-3n-30n^2=30n^3+33n^2+5n+2

    Таблицы и графики для варианта со случайными значениями.

    C1 = F(n)/T(n)

    C2 = O(F(n))/T(n)

    C3 = F(n)/NOP

    C4=O(F(n))/NOP

    645243,3

    1283422

    1,952207

    3,883042

    674354,5

    1345009

    2,05029

    4,089329

    672316

    1342171

    1,971009

    3,934801

    703233,5

    1404535

    2,085596

    4,165464

    705712,5

    1409874

    2,062588

    4,120643

    686506,4

    1371755

    2,006237

    4,0088

    680016,6

    1358965

    2,002489

    4,001834

    664723,2

    1328533

    1,977981

    3,953245

    658463,2

    1316122

    1,953695

    3,905003

    586332,8

    1172021

    1,958764

    3,915375



    n

    T nach

    T kon

    T kon- T nach

    NOP

    O(F(n))=60n^3

    F(n)

    200

    1013476

    1013850

    374

    123614431

    480000000

    241321002

    400

    1013850

    1016705

    2855

    939029298

    3840000000

    1,925E+09

    600

    1016705

    1026361

    9656

    3293685929

    1,296E+10

    6,492E+09

    800

    1026361

    1048233

    21872

    7374929461

    3,072E+10

    1,538E+10

    1000

    1048233

    1090790

    42557

    14560836054

    6E+10

    3,003E+10

    1200

    1090790

    1166372

    75582

    25863103223

    1,0368E+11

    5,189E+10

    1400

    1166372

    1287523

    121151

    41141138644

    1,6464E+11

    8,238E+10

    1600

    1287523

    1472509

    184986

    62166653822

    2,4576E+11

    1,23E+11

    1800

    1472509

    1738381

    265872

    89608129449

    3,4992E+11

    1,751E+11

    2000

    1738397

    2147946

    409549

    122593624357

    4,8E+11

    2,401E+11













    По графику c3 видно, что значения формулы и варианта со случайными числами сильно отличаются (больше чем в 2 раза). Докажем, что формула верна рассмотрев худший случай – элементы дека упорядочены в обратном порядке.
    Нас интересует только зависимость F(n) от NOP, для того чтобы убедиться, что формула верна.




    Поделитесь с Вашими друзьями:
  • 1   2   3   4




    База данных защищена авторским правом ©psihdocs.ru 2022
    обратиться к администрации

        Главная страница