मैं इस होमवर्क प्रश्न के बारे में कुछ समय से सोच रहा हूं। आकार एन की एक संख्या सरणी को देखते हुए, एक एल्गोरिदम डिज़ाइन करें जो उच्च 1.5 और तुलनाओं के साथ उच्च और निम्न मानों को पायेगा।एल्गोरिदम अधिकतम 1.5n तुलनाओं के साथ उच्च/निम्न संख्याओं को खोजने के लिए
मेरे पहली कोशिश थी
int high=0
int low= Number.MaxValue //problem statement is unclear on what type of number to use
Number numList[0 . . n] //number array, assuming unsorted
for (i=0, i < n, i++) {
if (numList[i] > high)
high = numList[i]
else if (numList[i] < low)
low = numList[i]
}
मेरे समस्या पाश से प्रत्येक यात्रा तीन में से एक संभावनाएं है है:
- कम मूल्य पाया जाता है - 1 तुलना
- उच्च मूल्य बना पाया जाता है - 2 तुलना
- न तो पाया जाता है - 2 तुलना
तो एक संपूर्ण सरणी ट्रैवर्सल के लिए, अधिकतम 2 एन तुलना की जा सकती है, जो 1.5n तुलनाओं की अधिकतम आवश्यकता की समस्या से बहुत रोना है।
इस तरह की समस्याओं में, सर्वोत्तम प्रारंभिक मूल्य पहला तत्व है। – wildplasser
@ विल्डप्लेसर, क्या आपका मतलब पहले तत्व मान के साथ उच्च और निम्न दोनों को प्रारंभ करना है? – Jason
हां। इससे मनमाना {निचला, उच्च} -थान संभव संभावित मूल्य चुनने से बचा जाता है। 'रिक्त सरणी' केस हमेशा विशेष होता है (यह * * न्यूनतम नहीं है, उच्चतम) – wildplasser