تلخيص صفيف وإختيار كبير

Question

كيفية العثور على خوارزمية لحساب قيمة المجموع في الصفيف؟

هل هذا شيء مثل هذا؟

Algorithm Array Sum
Input: nonnegative integer N, and array A[1],A[2],...,A[N]
Output: sum of the N integers in array A
Algorith Body:
j:=1
sum:=0
while j<N
      sum := sum + a[J]
      j:=j+1
  end while
end Algorithm Array Sum

وكيف يمكنني ربطه بوقت الجوار في الخوارزمية باستخدام O-Netation

هذا هو امتحان العام الماضي وأحتاج إلى إجراء مراجعة لامتحاني.

سؤال
يتم إعطاء صفيف A [] القابضة قيمة عدد صحيح
1. Give خوارزمية لحساب مجموع كل القيمة في الصفيف
2. أدق أبسط وأفضل تدوين O- وقت التشغيل من الخوارزمية.

Answer 1

السؤال هو العثور على مجموع كل القيم تكرر من خلال كل عنصر في الصفيف وإضافة كل عنصر إلى قيمة مجموع مؤقتة.

temp_sum = 0
for i in 1 ...array.length
    temp_sum = temp_sum + array[i]

منذ أن تحتاج إلى الذهاب من خلال جميع العناصر في الصفيف، هذا البرنامج يعتمد خطيا لعدد العناصر. وبعد إذا كان لديك 10 عناصر، فقم بتكرار من خلال 10 عناصر، إذا كان لديك مليون ليس لديك خيار آخر غير المضي قدما في جميع العناصر مليون وإضافة كل منها. وهكذا تعقيد الوقت هو θ (ن).

إذا كنت تجد مجموع جميع العناصر وأنت لا تعرف أي شيء حول البيانات، فأنت بحاجة إلى إلقاء نظرة على جميع العناصر مرة واحدة على الأقل. وهكذا ن هو البوليس. تحتاج أيضا إلى أن ننظر إلى العنصر أكثر من مرة. n هو أيضا الحد الأعلى. ومن هنا هو التعقيد θ (ن).

ومع ذلك، إذا كنت تعرف شيئا عن العناصر حول العناصر .. يمكنك الحصول على سلسلة من الأرقام الطبيعية N، يمكنك القيام بذلك في وقت ثابت مع N (N + 1) / 2. إذا كانت البيانات التي تحصل عليها عشوائي، فلن يكون لديك خيار سوى القيام بخوارزمية الوقت الخطي أعلاه.

Answer 2

حيث ن هو حجم الصفيف وكل ما عليك فعله هو تكرر من Begeinning لإنهاء التدوين الكبير o هو o [n

integer N= Size_array;
array a[N]
j=1 
sum=0
while j<=N 
 sum += a[j]  
 j++
end while

Answer 3

أعتقد أنك تعني "بينما ي <= n"، تحتاج إلى تحديد هذا.

يجب أن يكون وقت التشغيل O (ن)، كما أعتقد، كما لديك حلقة واحدة فقط.

Answer 4

لحساب O لهذه الخوارزمية، تحتاج إلى حساب عدد مرات تنفيذ كل سطر التعليمات البرمجية. في وقت لاحق، ستحسب العمليات الأساسية فقط ولكن تبدأ من خلال حساب الكل.

وبالتالي كم مرة سوف J: = 1 خط تشغيل؟ كم مرة سوف المبلغ: = 0 تشغيل؟ كم مرة سوف تنفذ حالة الحلقة؟ البيانات داخل الحلقة أثناء؟

مجموع هذه كل شيء. سوف تلاحظ أن القيمة التي تحصل عليها ستكون مثل 1 + 1 + N + N + N = 2 + 3N. وبالتالي يمكنك أن تستنتج أنها وظيفة خطية على n.