计算机科学-类库与数据结构

Labreport

Course:ClassLibrariesandDataStructures

Semester:1stsemesteroftheacademicyear2021-2022

Major:SoftwareEngineering

Class:2020

StudentName:温长银

StudentID:222020321062106

Teacher:ZHAO,Hengjun（赵恒军）

SchoolofComputerandInformationScience

NameTimeComplexityandRuntimeAnalysis

DateOct11,2021Type^Confirmatory

瓯esign

□Comprehensive

1.Objective&Requirements

a)Understandthetheoreticaltimecomplexityofanalgorithmand

knowhowtoanalyzeit

b)Grasptheuseofrandomnumbersandtechniquesformeasuring

executiontimeinC++

c)Graspruntimeanalysisofprogramstoshowtheeffectof

theoreticalcomplexityonthetimecostofrealprogramsby

runningprogramsandmeasuringthetimecost

2.Experimentalenvironment(platformandsoftware)

Windows7(orhigherversions)+VisualStudio2010(orhigher

versions)

1)Experimentalcontentanddesign(MainContent,Procedure,

CodesandResults)

Task1

1.Youareprovidedwithatemplatecontainerbasedonsingly

linkedlist.Pleasereadthesourcecodeandimplementanew

methodAddTail()thatcanaddanewelementattheendof

thelinkedlist.

2.YouareprovidedwithaCompanyandEmployeeclass.Please

implementtwomethodsfortheCompanyclassi.e.

•voidinputEmployeeHead(intn);

•voidinputEmployeeTail(intn);

Theintegernisthemethodargumentthatspecifiesthe

totalnumberofemployeetoinput.inputEmployeeHead()is

basedonAddHead()andinputEmployeeTail()isbasedon

AddTail().Foreachnewemployee,itsnameisofformat

“Employee+ID”,e.g."Employeel23",anditsgrosspay

isarandomlygeneratedinteger.

3.Usingruntimeanalysistomeasurethetimecostsof

inputEmployeeHeadandinputEmployeeTailbyincreasingthe

totalnumberofemployeen,e.g.n=1000,2000,10000,

20000,100000,andsoon.Recordthetimecostsofthe

twomethodsforeachn.Plotthedatainafigureandtrytofit

thedatausingacurve(数据拟合，曲线拟合)。

4.Analyzethetheoreticaltimecomplexityof

inputEmployeeHeadandinputEmployeeTail.Compareyour

theoreticalanalysistotheexperimentaldatayouobtained.

Stepl.

readthesourcecodeandimplementanewmethodAddTail()thatcan

addanewelementattheendofthelinkedlist.

Step2：

implementtwomethodsfortheCompanyclassi.e.

•voidinputEmployeeHead(intn);

•voidinputEmployeeTail(intn);

Theintegernisthemethodargumentthatspecifiesthe

totalnumberofemployeetoinput.inputEmployeeHead()is

basedonAddHead()andinputEmployeeTail()isbasedon

AddTail().Foreachnewemployee,itsnameisofformat

“Employee+ID”,e.g."Employeel23",anditsgrosspay

isarandomlygeneratedinteger.

^defineNULL0

template<classT>

classListTemp

(

private:

structNode

(

Tdata;

Node*next;

};

Node*head;

intsize;

public:

ListTempO;

“ListTemp();

intgetLengthOconst;

boolisEmpty0const;

voidAddHead(constT&newData);

voidAddTail(constT&newData);

)；

template<classT>

ListTemp<T>::ListTemp0

(

head=NULL;

size=0;

)

template<classT>

ListTemp<T>::^ListTempO

(

Node*current=head;

Node*temp=NULL;

while(current!=NULL)

(

temp=current;

current=current->next;

deletetemp;

)

)

template<classT>

intListTemp<T>::getLengthOconst

returnsize;

)

template<classT>

boolListTemp<T>::isEmptyOconst

(

returnsize==0;

)

template<classT>

voidListTemp<T>::AddHead(constT&newData)

(

Node*temp=newNode;

temp->next=head;

temp->data=newData;

head=temp;

size++;

)

template<classT>

voidListTemp<T>::AddTail(constnewl)；ii(i)

(

//pleaseimplementthis

Node*temp=newNode;

temp->data=newData;

Node*ptr=head;

while((ptr->next)!=NULL)

ptr=ptr->next;

temp->next=NULL;

ptr->next=temp;

size++;

}

#endif

^include“company,h”

ttinclude<iostream>

usingnamespacestd;

voidCompany::inputEmployeellead(intn)

(

//pleaseimplementthis

for(inti=0;i<n;i++)

(

srand((unsignedint)time(0));

strings="Employee”;

stringres=s+to_string(n);

intpay=rand();

Employeeemp(res,pay);

container.AddHead(emp);

)

)

voidCompany::inputEmployeeTail(intn)

(

for(inti=0;i<n;i++)

(

srand((unsignedint)time(0));

strings="Employee”;

stringres=s+to_string(n);

intpay=rand();

Employeeemp(res,pay);

container.AddTail(emp);

)

)

^includeTistTemp.h"

ttinclude"company,h”

ttinclude<ctime>

#include<ioslream>

usingnamespacestd;

intmainO

(

clockibeginl,endl,timel,begin2,end2,time2;

for(intnum=1000;num<100000;num+=1500)

(

Companyemp;

beginl=clock();

emp.inputEmployeeHead(num);

endl=clock();

timel=endl-beginl;

begin2=clock();

emp.inputEmployeeTai1(num);

end2=clock0;

time2=end2-begin2;

cout<<timel<<endl;

cout<<time2<<endl;

)

return0;

)

Result:

HEAD:

X

LinearmodelPolyl:

f(x)=pl*x+p2

Coefficients(with95%confidencebounds):

pl=10.21(9.848,10.57)

p2=-3.495(-7.818,0.8281)

Goodnessoffit:

SSE:353.1

R-square:0.9949

AdjustedR-square:0.9946

RMSE:4.429

Tail:

10000

A5000-

•yvs.x

_.44untitledfit1

o—।iiiiii।

2468101214161820

X

LinearmodelPoly2:

f(x)=pl*xA2+p2*x+p3

Coefficients(with95%confidencebounds):

pl=30.39(28.25,32.54)

p2=-119.2(-165.5,-72.94)

p3=286.8(75.83,497.9)

Goodnessoffit:

SSE:3.072e+05

R-square:0.9984

AdjustedR-square:0.9982

RMSE:134.4

AnswerforAdditionalquestions

Ifthenewnodeisinsertedintothetailofthecurrentlinkedlist,thetimecomplexity

isthesameasthatoftheheaderinsertionmethod.

3.Resultanalysisanddiscussion(Analysisofexperimentalresults

andsumminguptheharvestandtheexistingproblems)

Theheadinsertionmethodisusedtoestablishasinglelinkedlist.Theorderof

readingdataisoppositetotheorderofelementsinthegeneratedlinkedlist.The

insertiontimeofeachnodeis0(1).Ifthelengthofthesinglelinkedlistisn,thetotal

timecomplexityis0(n).

Toestablishasinglelinkedlistbyheadinterpolation,youneedtotraversethe

linkedlist.Theinsertiontimeofeachnodeis0(n).Ifthelengthofthesinglelinked

listisn,thetotaltimecomplexityisO(n2)

UndertheguidanceofMr.Zhao,1un