የውህደት አይነት ውስብስብነት እንዴት ይሰላል?

2024 ደራሲ ደራሲ: Lynn Donovan | [email protected]. ለመጨረሻ ጊዜ የተሻሻለው: 2023-12-15 23:42

2 መልሶች. የመስቀለኛ ክፍል A[L፣ R] ወደ ሁለት አንጓዎች መከፋፈል R-L+1 ጊዜ እና ከዚያ ይወስዳል መቀላቀል ሁለቱ የሕጻናት አንጓዎች A[L, M] እና A[M+1, R] እንደገና A[R-L+1] ጊዜ ይወስዳል። ስለዚህ ለእያንዳንዱ መስቀለኛ መንገድ, የክዋኔዎች ብዛት አልጎሪዝም የሚሰራው ከዛ መስቀለኛ መንገድ ጋር ከሚዛመደው የድርድር መጠን ጋር እኩል ነው።

ይህንን በተመለከተ ውህደት መደርደር እንዴት ይሠራል?

የውህደት መደርደር ክፋይ እና አሸናፊን እንዴት እንደሚጠቀም እነሆ፡-

1. በ p እና r መካከል መሃል ያለውን ቦታ q ቁጥር በማግኘት ያካፍሉ።
2. በክፍልፋይ ደረጃ በተፈጠሩት በእያንዳንዱ ሁለት ንኡስ ችግሮች ውስጥ ያሉትን ንዑስ ክፍሎችን ደጋግመው በመደርደር ያሸንፉ።
3. ሁለቱን የተደረደሩትን ንዑስ ክፍሎችን በማዋሃድ ወደ ነጠላ የተደረደሩ ንዑስ ድርድር[ገጽ.

እንዲሁም፣ ለማዋሃድ ትልቅ ኦ ውስብስብነት ምንድነው? አዋህድ ደርድር የተረጋጋ ነው መደርደር ይህም ማለት በድርድር ውስጥ ያለው ተመሳሳይ አካል አንዳቸው ከሌላው አንፃር የመጀመሪያውን ቦታቸውን ይጠብቃሉ ማለት ነው። አጠቃላይ ጊዜ ውስብስብነት የ መደርደር አዋህድ ነው። ኦ (nLogn)። በጣም በከፋ ሁኔታ ውስጥ ስለሆነ የሩጫ ጊዜው በጣም ውጤታማ ነው ኦ (nlogn) ቦታው ውስብስብነት የ መደርደር አዋህድ ነው። ኦ (n)

በከፋ ሁኔታ ውስጥ የመዋሃድ ውስብስብነት ምንድነው?

n*log(n)

መደርደር ምን ያህል ንጽጽሮችን ይፈጥራል?

በአንደኛው ዝርዝር ውስጥ ያሉትን ንጥረ ነገሮች ስናልቅ የቀሩትን ንጥረ ነገሮች በመጨረሻዎቹ ክፍተቶች ውስጥ እናስገባቸዋለን ተደርድሯል ዝርዝር. ከዚህ የተነሳ, መቀላቀል በድምሩ n ንጥረ ነገሮች ያላቸው ሁለት ዝርዝሮች ቢበዛ n-1 ያስፈልጋቸዋል ንጽጽር.