Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
greendaizer
0 / 0 / 0
Регистрация: 20.01.2013
Сообщений: 70
#1

Нужно посчитать сложность алгоритма - C++

01.12.2013, 22:23. Просмотров 352. Ответов 2
Метки нет (Все метки)

Дорогие обитатели форума, нужно посчитать сложность рекурсивной функции удаления вершин из бинарного дерева. К сожалению, не представляю, как это можно сделать =( В задании сказано воспользоваться некой формулой и посчитать в общем случае, а затем в самом коде добавить какую-то переменную, которая поможет сосчитать сложность в конкретных случаях.

Программа:
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
#include<iostream>
#include<conio.h>
#include<time.h>
using namespace std;
 
struct tree
{
       int info;
       tree *right, *left; 
};
 
tree* bt=NULL;
 
void push(int a, tree **t)
{
    if((*t)==NULL)
    {
        (*t)=new tree;
        (*t)->info=a;
        (*t)->left=(*t)->right=NULL; 
        return;
    }
    if(a>(*t)->info)
        push(a,&(*t)->right); 
    else
        push(a,&(*t)->left); 
};
 
void print(tree *t, int l)
{
  if(t!=NULL)
  {
    print(t->right, l+1);
    for(int i=0; i< l; i++)
        cout<< "   ";
        printf("%4ld", t->info);
        print(t->left, l+1);
  }
  else cout<<endl;
};
 
void count(tree *t, int & c)
{
  if(t!=NULL)
  {
    c=c+1;
    count(t->left, c);
    count(t->right, c);
  }
};
 
void check(tree *t, bool & f, int c)
{
  if(t!=NULL)
  {
    if(t->info==c)
        f=true;
    check(t->left, f, c);
    check(t->right, f, c);
  }
};
 
 
void Delete(tree** t)
{
  if((*t)!=NULL)
  {
      if ((((*t)->left==NULL||(*t)->right==NULL))&&!((*t)->left==NULL&&(*t)->right==NULL))
    {
      tree* ptr=(*t);
      if((*t)->left==NULL&&(*t)->right==NULL) 
          (*t)=NULL;
      else 
          if((*t)->left==NULL)
              (*t)=ptr->right;
          else
              if((*t)->right==NULL)
              (*t)=ptr->left;
      else
      {
        (*t)=ptr->right;
        tree **ptr1;
        ptr1=t;
        while(*ptr1!=NULL) 
          ptr1=&((*ptr1)->left);
        (*ptr1) = ptr->left;
      }
      delete(ptr);
      Delete(t);
    }
    else {
      Delete(&((*t)->left));
      Delete(&((*t)->right));
    }
  }
};
 
 void DeleteTree(tree* t)
 {
  if(t!=NULL)
  {
    DeleteTree(t->left);
    DeleteTree(t->right);
    delete(t);
  }
};
 
int main()
{
    int n;
    cin>>n;
 
    for(int i=0; i<n; i++)
    {
        int s;
        cin>>s;
        push(s, &bt);
    }
    print(bt, 0);
    Delete(&bt);
    cout<<endl;
    print(bt, 0);
 
    //Test1//
    int c=0;
    count(bt,c);
    cout<<"Kol-vo vershin= "<<c<<endl;
 
    //Test2//
    bool f=false;
 
    cout<<"Vvedite vershinu, nalichie kotoroi hotite proverit`"<<endl;
    cin>>c;
    check(bt, f, c);
    if(f)
        cout<<"Vershina prisutstvuet"<<endl;
    else
        cout<<"Takoi vershiny v dereve net"<<endl;
 
    //Test3//
    DeleteTree(bt);
    if(bt!=NULL)
        print(bt,0);
    else
        cout<<"Dereva net"<<endl;
    
    getch();
    return 0;
}
Функция, с которой нужно работать:
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
void Delete(tree** t)
{
  if((*t)!=NULL)
  {
      if ((((*t)->left==NULL||(*t)->right==NULL))&&!((*t)->left==NULL&&(*t)->right==NULL))
    {
      tree* ptr=(*t);
      if((*t)->left==NULL&&(*t)->right==NULL) 
          (*t)=NULL;
      else 
          if((*t)->left==NULL)
              (*t)=ptr->right;
          else
              if((*t)->right==NULL)
              (*t)=ptr->left;
      else
      {
        (*t)=ptr->right;
        tree **ptr1;
        ptr1=t;
        while(*ptr1!=NULL) 
          ptr1=&((*ptr1)->left);
        (*ptr1) = ptr->left;
      }
      delete(ptr);
      Delete(t);
    }
    else {
      Delete(&((*t)->left));
      Delete(&((*t)->right));
    }
  }
Заранее спасибо!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.12.2013, 22:23     Нужно посчитать сложность алгоритма
Посмотрите здесь:

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

Определить сложность алгоритма - C++
для i от 1 до n нц s = 0; для j от 1 до n нц s = s + a * x; кц ...

Временная сложность алгоритма - C++
Всем привет! Пусть есть натуральные числа а и n. Найти a в степени n. Временная сложность алгоритма должна быть О(log2n)

Временная сложность алгоритма - C++
Помогите посчитать временную сложность след. алгоритма. Желательно с объяснениями, а не просто результат. #include &lt;iostream&gt; #include...

Определить сложность алгоритма - C++
Ребята подскажите сложность алгоритма:) Функция ищет максимальный элемент в двухмерном массиве. Это будет n*m или n^2? int*...

Как рассчитать сложность алгоритма? - C++
Помогите мне пожалуйста Я не понимаю много о сложности алгоритма. Как рассчитывать сложность алгоритма в этом коде? #include...

Как узнать сложность алгоритма(ресурсы ,способы) - C++
Здравствуйте, нужно узнать сложность какой-нибудь ф-ии из стандартной библиотеки cpp. Где это можно узнать? Например max_element(it it)...

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

Нужно оптимизировать программу сложность с циклами и условными операторами - C++
Здравствуйте. Недели 2 пытаюсь кодить на с++, что-то получается, что-то не очень. Прошу отвечать только по существу. За указания на...

Сложность с матрицей. Нужно было сформировать вектор с строки с меньшим весом - C++
#include &lt;iostream&gt; #include &lt;iomanip&gt; #include &lt;cmath&gt; using namespace std; const int n=5, m=3; double a ; double...


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Nick Alte
Эксперт С++
1608 / 1000 / 118
Регистрация: 27.09.2009
Сообщений: 1,927
Завершенные тесты: 1
01.12.2013, 22:35     Нужно посчитать сложность алгоритма #2
Непонятно, что имеется под "сложностью" в данном случае. Обычную алгоритмическую сложность прикинуть элементарно: при удалении дерева удаляется каждая из вершин, причём каждая вершина посещается один раз, так что сложность O(n), где n - количество вершин.
Приведённые хитроумные конструкции заставляют подозревать, что имеется в виду какое-то совершенно другое понятие сложности, с не пойми какой метрикой.
greendaizer
0 / 0 / 0
Регистрация: 20.01.2013
Сообщений: 70
01.12.2013, 22:47  [ТС]     Нужно посчитать сложность алгоритма #3
Если это облегчит задачу, то при подсчёте этой сложности учитываются всякие присваивания, арифметические операции и вся эта ерунда из функции
Yandex
Объявления
01.12.2013, 22:47     Нужно посчитать сложность алгоритма
Ответ Создать тему
Опции темы

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