Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/6: Рейтинг темы: голосов - 6, средняя оценка - 5.00
0 / 0 / 0
Регистрация: 04.10.2014
Сообщений: 16
1

Временная сложность алгоритма

09.11.2014, 17:42. Показов 1072. Ответов 3
Метки нет (Все метки)

Помогите посчитать временную сложность след. алгоритма. Желательно с объяснениями, а не просто результат.
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
#include <iostream>
#include <ctime>
 
using namespace std;
 
int k = 0;
 
void sortShell(int massiv[], int razmer){
    int h, Tmp, j;
    h = razmer;
    h = h / 2;
    while (h > 0){
        for (int i = 0; i < razmer - h; i++){
            j = i;
            while (j >= 0 && massiv[j] > massiv[j + h]){
                Tmp = massiv[j + h];
                massiv[j + h] = massiv[j];
                massiv[j] = Tmp;
                j--;
            }
        }
        h = h / 2;
    }
}
 
void poisk(int massiv[], int razmer){
    for (int i = 0; i < razmer; i++){
 
            if (massiv[i] != massiv[i + 1] && massiv[i] != massiv[i - 1]){
                cout << massiv[i] << " ";
                k++;
            }
        
    }
}
 
int main(){
    setlocale(LC_ALL, "rus");
 
    int razmer;
 
    cout << "Введите размер массива: " << endl;
    cin >> razmer;
    while (cin.fail() || razmer <= 0){
        cin.clear();
        cin.ignore(numeric_limits<streamsize>::max(), '\n');
        cout << "Введено некорректное значение. Повторите ввод: ";
        cin >> razmer;
    }
 
    int *massiv = new int[razmer];
 
    srand(time(NULL));
    cout << "Исходный массив: ";
    for (int i = 0; i < razmer; i++){
        massiv[i] = 0 + rand() % 10;
        cout << " " << massiv[i];
    }
    cout << endl;
 
    sortShell(massiv, razmer);
    cout << "Отсортрованный массив: ";
    for (int i = 0; i < razmer; i++){
        cout << " " << massiv[i];
    }
    cout << endl;
 
    cout << "Неповторяющиеся числа: ";
    poisk(massiv, razmer);
    cout << endl;
 
    if (k == 0){
            cout << "Неповторящихся чисел нет!" << endl;
        }
    else{
        cout << "Всего в массиве " << k;
        if (k == 1){
            cout << " неповторяющееся число." << endl;
        }
        else if ((k > 1) && (k < 5)){
            cout << " неповторяющихся числа." << endl;
        }
        else{
            cout << " неповторяющихся чисел." << endl;
        }
    }
 
    delete[] massiv;
    massiv = NULL;
    system("pause");
    return 0;
}
__________________
Помощь в написании контрольных, курсовых и дипломных работ здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
09.11.2014, 17:42
Ответы с готовыми решениями:

Временная сложность алгоритма
Всем привет! Пусть есть натуральные числа а и n. Найти a в степени n. Временная сложность...

Какова временная сложность метода ветвей и границ, и генетического алгоритма, которые решают задачу о рюкзаке?
Всем привет!Не подскажете какова временная сложность метода ветвей и границ,и генетического...

Временная сложность алгоритмов
Добрый вечер. Требуется разработать ПО обеспечивающие анализ временной сложности некоторых...

Временная оценка алгоритма
Уважаемые форумчане, помогите сделать временную оценку выполнения рекурсивных алгоритмов (или хотя...

3
65 / 65 / 54
Регистрация: 23.09.2012
Сообщений: 212
09.11.2014, 17:51 2
Все, кроме сортировки вроде как за O(N) работает. Сортировка Шелла за O(N^2) в худшем случае.

Соответственно весь алгоритм работает за O(N^2)
0
0 / 0 / 0
Регистрация: 04.10.2014
Сообщений: 16
09.11.2014, 17:58  [ТС] 3
grikukan, можете поподробнее рассказать, как подсчитали?
0
65 / 65 / 54
Регистрация: 23.09.2012
Сообщений: 212
09.11.2014, 18:00 4
То что сортировка Шелла работает за квадрат, написано в википедии.
А остальное - это линейные проходы по массиву за O(N)
O(N^2)+O(N)=O(N^2)
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
09.11.2014, 18:00

Определить сложность алгоритма
Нужно определить сложность этого алгоритма. И было бы не плохо если бы вы объяснили как определить...

Определить сложность алгоритма
Ребята подскажите сложность алгоритма:) Функция ищет максимальный элемент в двухмерном массиве....

Определить сложность алгоритма
для i от 1 до n нц s = 0; для j от 1 до n нц s =...

Определить сложность алгоритма
Помогите , пожалуйста, выполнить задания. Буду благодарен за объяснение , так как не понимаю как...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru