Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Кансег
0 / 0 / 1
Регистрация: 09.01.2013
Сообщений: 41
#1

получить аналитическую оценку трудоемкости работы алгоритма сортировки, используя О-символику

13.11.2014, 03:50. Просмотров 267. Ответов 0
Метки нет (Все метки)

Добрый!

Есть код: стек через указатели с сортировкой вставкой.
Помощь требуется в подсчете F(n) сортировки push_sorted_stack.
Предполагаю (xDDD), что O(F(n)) = n^2.
F(n) не хочет уверено просчитываться.


C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
#include <stdlib.h>
#include <stdio.h>
#include <iostream>
#include <conio.h>
#include <time.h>
#include <chrono>
 
int nop;
int quant_elem = 2000;
 
 
typedef struct stack{
    int value;              /* информативная часть */
    struct stack * next;    /* адресная часть */
} node_t, stack_t;
 
 
/* Функция позволяет определить есть ли элементы в стеке, в качестве аргумента принимает двойной указатель на вершину стека.
* Если стек пуст, то указатель на вершину должен быть равен NULL.
*/
int is_empty(stack_t ** top){
    nop = nop + 3;
    return *top == NULL;        //1
}
 
/* Положить элемент в стек. */
void push(stack_t ** top, int value){
    node_t *node = (node_t *)malloc(sizeof(node_t));
 
    /* формирование информативной части */
    node->value = value;
 
    /* формирование адресной части */
    node->next = NULL;
 
    nop = nop + 4;
 
    /* если стек не пуст, то вершина должна указывать на предыдущий элемент */
    if (!is_empty(top)){
        node->next = *top;
        nop = nop++;
    }
    (*top) = node;
}
 
/* Функция удаления элемента с вершины стека */
void pop(stack_t **top){
    node_t *node;
    /* Если стек пуст, то удалять ничего не надо */
    if (!is_empty(top)){
        /* Так как удаляется вершина стека, то адресную часть необходимо скорректировать */
        node = *top;
        *top = (*top)->next;
        free(node);
        node = NULL;
        nop = nop + 4;
    }
}
 
/* Извлечение значения из стека
Функция возвращает значение из вершины стека
*/
int top(stack_t **top){
    nop = nop + 2;
    if (!is_empty(top)){
        nop++;
        return (*top)->value;
    }
    else{
        nop++;
        return 0;
    }
}
 
/* Очистка стека. Функция удаляет все элементы из стека*/
void clear(stack_t **top){
    while (!is_empty(top)){
        pop(top);
        nop = nop + 2;
    }
}
 
/* Вывод стека на экран */
void print(stack_t **top){
    node_t *node;
    for (node = *top; node != NULL; node = node->next){
        printf("%d ", node->value);
        nop++;
        nop++;
    }
    printf("\b\b\b   \n");
    nop++;
}
 
//Сортировка методом простоой вставки
//интерфейс был: указатель на стек и значение(элемент)
 
void push_sorted_stack(stack_t ** top, int value) {
 
   // доп стек
    stack_t * values = NULL;        //1
   
   //вершина
   int top_dop=NULL;                //1
   
   nop=nop+2;
   
   /*инициализация стека вершина = 0 
   init_stack(&values);*/
 
   // пока основной стек не пустой
   while (!is_empty(top)) {         //
        
        // вершину присваиваем 
        top_dop =  (*top)->value;   //2
        
        nop++;
 
    //При вставке элемента в стек идет проверка, не меньше ли вставляемый элемент последнего элемента стека. 
    //Если вставляемый элемент меньше верхнего, то верхний извлекается и перегоняется в дополнительный стек, 
        
 
        //Если вершина меньше или равна эл  
        if (top_dop <=  value) {    //1
                 break;
            }
        //в доп стек вставляем эл 
        push(&values, top_dop);
 
        // из основного стека выталкиваем
        pop(top);
 
        nop=nop+2;   
   }
 
 
    //вставляем в основной стек эл
   push(top, value);
    
   nop++;
 
    //пока доп стек не пустой
   while (!is_empty(&values)) {
      
      //добавляем в основной стек вершину доп стека
       push(top, values->value);
      
      // выталкиваем из доп стека
      pop(&values);
      nop=nop+2;
   }
}
 
 
 
int main() {
 
    //запил уникальных значений при включении рандома
    srand(static_cast<unsigned int>(time(NULL)));
 
    //Включение русского языка в консоли 
    setlocale(LC_ALL, "Rus");
    
    time_t time;
    nop = 0;
 
    stack_t *sorted = NULL;
    stack_t *unsorted = NULL;
 
    int i;
    int k,g = 0;
    
 
    printf("Сортировка методом вставки на АТД \"Cтек\" ");
    
 
    /* заполняем стек */
    printf("\n-----------------------------------------------\nзаполняем rand'мом" );
    
    
    nop=nop+5;
    time = clock();
 
 
    for (i = quant_elem; i > g; --i){
        k= rand()%1000;
        push(&unsorted, k );
        push_sorted_stack(&sorted, k);
        nop=nop+5;}
        
        printf("\n\nunsorted: ");
        print(&unsorted);
        printf("\nsorted:   ");
        print(&sorted); 
        
 
        time = clock()-time;
        //((float)time) / CLOCKS_PER_SEC)
        //(float)(clock() - time) / 1000)
        printf("\nTIME (%f секунд) ",((float)time) / CLOCKS_PER_SEC);
        printf ("\nNOP %d", nop);
 
        nop = 0;
 
    /* статическое заполнение,  значение = остаток от деления
    
        printf("\n-----------------------------------------------\nзаполняем статичными значениями" );
        nop= 0;
        sorted = NULL;
        unsorted = NULL;
        
        for (i = 10; i > 0; --i) {
      push(&unsorted, (i * 17) % 25);}
        printf("\n\nunsorted: ");
        print(&unsorted);
      
        time = clock();
      for (i = 9; i > -1; --i) {
        push_sorted_stack(&sorted, (i * 17) % 25); }
        printf("\nsorted:   ");
        print(&sorted);
        
        printf("\nTIME %f ",(float)(clock() - time) / 1000);
        printf ("\nNOP %d", nop);
        */
    
    
        
    _getch();
 
   return EXIT_SUCCESS;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.11.2014, 03:50
Ответы с готовыми решениями:

Получить аналитическую оценку трудоемкости работы алгоритма сортировки
есть код программы и нужно вычислить трудоемкость алгоритма, а то какая-то шляпа получилась....

Время работы алгоритма пирамидальной сортировки массива
Чему равно время работы алгоритма пирамидальной сортировки массива A длины n, в котором элементы...

Время работы алгоритма сортировки
Есть такой код сортировки наивным методом: public static int msp1(int X) { int maxteilsumme...

Подсчёт время работы алгоритма сортировки
Пытаюсь посчитать время работы алгоритма в миллисекундах, но постоянно выходит минусовое число....

вычисления функции трудоемкости алгоритма
есть у меня некий алгоритм, в коментариях росписани к-чество операций for (int i = 0; i &lt;...

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.11.2014, 03:50

Записать числа двух упорядоченных массивов в массив С в том же порядке, не используя алгоритма сортировки.
Помогите решить задачу используя процедуры: Создать два одномерных массива А и В различной...

Оценки трудоемкости быстрой, пирамидальной, пузырьковой сортировки по времени и обьему памяти
Мне очень нужно оценки трудоемкости быстрой, пирамидальной, пузырьковой сортировки по времени и...

Запишите рекуррентное уравнение для времени работы этой рекурсивной версии алгоритма сортировки вставкой
Как записать рекуррентное уравнение для времени работы . Сортировку вставкой можно представить в...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru