The Spanning Tree based Approach for Solving the Shortest Path Problem in Social Graphs



Download 0,63 Mb.
Pdf ko'rish
bet10/18
Sana02.01.2022
Hajmi0,63 Mb.
#308113
1   ...   6   7   8   9   10   11   12   13   ...   18
4.3

 

Time and Space Complexity 

To  measure  the  time  complexity  of  the 



Atlas

algorithm,  analysis  of  the  each  step  is  needed. 



Finding  of  the  shortest  path  in  a  tree  takes  time 

linear  with  regards  to  the  depth 



L

  of  the  tree 



O(L)

Search  of 



k

  shortest  paths  in 



k

  trees  takes  time 



O(kL)

.  The  number  of  edges  queried  by  the 



Atlas

algorithm  is  bounded  by 



dkL

,  where 



d

 is  the 

maximal  degree  of  vertices  in  the  original  social 

graph.  Thus,  the  breadth-first  search  algorithm 

works  in 

O(dkL) 

in  the  worst  case.  Thus,  the 

summarized  time  complexity  of  the  proposed 

shortest  path  searching  algorithm  depends  on  the 

depth  of  trees,  number  of  trees  and  the  maximal 

degree of vertices  in  the social  graph  and  equals  to 



O(dkL)

. Also, some social networking sites limit the 

maximal number of friends. Therefore, 

d

 is assumed 

to be a constant. 

The time complexity of 



Atlas

 algorithm is 



O(kL)

since  the  algorithm  searches  for  shortest  paths  in 



k

 

spanning trees. Thus, the time complexity of 



Atlas

is worse than the one of 



Atlas

The  number  of  edges  queried  by 



Atlas

+  is 


O(dkL)

,  therefore,  its  space  complexity  is 



O(dkL)

While 



Atlas

  requires 



O(L)

  memory.  Thus, 



Atlas

requires more memory than 



Atlas.

 


Download 0,63 Mb.

Do'stlaringiz bilan baham:
1   ...   6   7   8   9   10   11   12   13   ...   18




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish