Предыдущий пост -
Следующий пост -

O – нотация.

Рубрика: C++, Дата: 14 May, 2013, Автор:

Изучите О – нотацию (параграф 17.1.2). Выполните измерения для операций стандартных контейнеров с целью определения числовых коэффициентов вовлеченных в О – нотацию.

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

И еще что такое О-нотация? Это просто выражение которое показывает зависимость времени выполнения программы от количества элементов. Есть прямолинейная зависимость например О(n) – это показывает, что чем больше элементов в векторе тем операции вставки в средину вектора и удаления из средины, которые применяются к спискам будут прямо пропорционально зависеть от количества элементов в нем. Чем меньше элементов тем время меньше, и чем больше элементов тем время больше. В общем линейная зависимость.

Приведу вам код, конечно он не решение задачи, просто как бы общий смотр контейнеров.

//programma dl9 raccheta koeficientov O-notacii
//dl9 ctandartnux kontainerov
#include <iostream>
using std::cout;
using std::endl;
#include <vector>
using std::vector;
#include <ctime>
using std::time;
#include <cstdlib>
using std::exit;
using std::rand;
using std::srand;
#include <list>
using std::list;
#include <deque>
using std::deque;
#include <stack>
using std::stack;
#include <queue>
using std::queue;
using std::priority_queue;
#include <map>
using std::map;
using std::multimap;
#include <string>
using std::string;
#include <utility>
using std::pair;
#include <set>
using std::set;
using std::multiset;
#include <array>
using std::array;
#include <valarray>
using std::valarray;
#include <bitset>
using std::bitset;


int main()
{
	clock_t begin,end;
	double time_spend;
	
	double k_vector;

	srand(time(0));
	cout <<"racchet koeficientov dl9 vector"<<endl;
	vector<int>vec1(10000,5);

	begin=clock();
	vec1.insert((vec1.begin()+4),35);
	end=clock();
	time_spend=(double)(end-begin)/CLOCKS_PER_SEC;
	cout <<"vrem9_insert_1 = "<<time_spend<<endl;

	k_vector=time_spend/10000;
	cout <<"k= "<<k_vector<<endl;

	//naxodim koeficient dl9 list
	list<int> lis(10,5);
	list<int> lis1(1000,5);

	begin=clock();
	lis1.insert(lis1.begin(),35);
	end=clock();
	time_spend=(double)(end-begin)/CLOCKS_PER_SEC;
	cout <<"time_spend= "<<time_spend<<endl;//для списка постоянная операция очень быстрая

	//проверка deque
	deque<int> deq1(100000, 5);

	begin=clock();
	deq1.insert(deq1.begin()+4, 35);
	end=clock();
	cout <<"begin= "<<begin<<endl;
	cout <<"end= "<<end<<endl;
	time_spend=(double)(end-begin)/CLOCKS_PER_SEC;
	cout <<"time_spend= "<<time_spend<<endl;
	//как мы видим мы даже время не можем засеч стремится к нулю поэтому мы тут не посчитаем коефициент.

	//посмотрим stack
	stack<int> stac;
	//тут как мы видим мы можем только добавлять элементы с канча и с конца извлекать 
	stac.push(3);
	cout <<"stac.size()= "<<stac.size()<<endl;
	cout <<"stac.top()= "<<stac.top()<<endl;
	stac.pop();
	cout <<"stac.size()= "<<stac.size()<<endl;
	//cout <<stac.pop()<<endl;
	//просто протестили и так следущий контейнер

	//а теперь посмотрим queue
	queue<int> que;
	cout <<"que.size()= "<<que.size()<<endl;
	que.push(1);
	que.push(2);
	cout <<"que.size()= "<<que.size()<<endl;
	cout <<que.front()<<endl;
	cout <<"que.size()= "<<que.size()<<endl;
	que.pop();
	cout <<que.front()<<endl;
	cout <<"que.size()= "<<que.size()<<endl;
	
	//так тестим следущий контейнер
	//priority_queue
	priority_queue<int> priority;
	priority.push(4);
	priority.push(3);
	cout <<"priority.size()= "<<priority.size()<<endl;
	cout <<priority.top()<<endl;// большее число всегда вперед попадает по умолчанию less

	//теперь протестим map
	map<int,int> mass;
	cout <<"mass.size()= "<<mass.size()<<endl;
	mass[0]=3;
	mass[1]=4;
	cout <<mass[0]<<endl;
	cout <<mass[1]<<endl;
	cout <<"mass.size()= "<<mass.size()<<endl;
	mass.clear();
	cout <<"mass.size()= "<<mass.size()<<endl;

	//тест multimap
	multimap<int,int> mass1;
	typedef pair<int,int> p;//tip p kak pair<int,int>
	cout <<"mass1.size()= "<<mass1.size()<<endl;
	mass1.insert(pair<int,int>(3,4));
	mass1.insert(pair<int,int>(4,2));
	cout <<"mass1.size()= "<<mass1.size()<<endl;

	//Тестирование set

	set<int> se;
	cout <<"se.size()= "<<se.size()<<endl;
	for(int i=1;i<=100;i++)
		se.insert(i);
	cout <<"se.size()= "<<se.size()<<endl;
	for(int i=2;i<=100;i+=2)
		se.erase(i);
	cout <<"se.size()= "<<se.size()<<endl;
	//vucheclenie cymmu elementov
	int sum(0);
	for(set<int>::iterator it=se.begin(); it!=se.end();++it)
	{
		cout <<*it<<' ';
		sum+=*it;
	}
	cout <<endl;
	cout <<"sum= "<<sum<<endl;
	//ладно с set разобрались попробуем, протестировать multiset

	//тест multiset
	multiset<int> multise;
	cout <<"multise.size()= "<<multise.size()<<endl;
	for(int i=1;i<=100;i++)
		multise.insert(i);
	cout <<"multise.size()= "<<multise.size()<<endl;
	for(int i=1;i<=100;i++)
		multise.insert(i);
	cout <<"multise.size()= "<<multise.size()<<endl;

	//тест контейнера string
	
	string str;
	str="hellow world gacpada";
	//вывод с помощью итератора
	for(string::iterator it=str.begin();it!=str.end();++it)
		cout <<*it<<' ';
	cout <<endl;

	//тест array
	array<int, 8> arra;
	cout <<"arra.size()= "<<arra.size()<<endl;
	for(int i=0;i<arra.size();i++)
		arra[i]=i;
	cout <<"arra.back()= "<<arra.back()<<endl;
	cout <<"arra.size()= "<<arra.size()<<endl;
	cout <<"arra.max_size()= "<<arra.max_size()<<endl;
	
	//тест valarray
	valarray<int> valarra(5);
	cout <<"valarra.size()= "<<valarra.size()<<endl;
	for(int i=0;i<valarra.size();i++)
	{
		valarra[i]=i;
		cout <<valarra[i]<<' ';
	}
	cout <<endl;
	cout <<"valarra.size()= "<<valarra.size()<<endl;

	//тест bitset
	bitset<10> bit;
	cout <<"bit.size()= "<<bit.size()<<end; 
	//вообщем bitset темный лес.

	return 0;
}

Да и все. Конечно не правильно никаких коэффициентов я не рассчитал, но все же хоть ознакомился с контейнерами.

rss