حساب ال Running Times فى اى خوارزميه؟

كل عام وانتم بخير ..... مفيش حد هيساعدنى فى فهمها :)

الاخت الفاضله مرحبا بك في قسم الرياضيات والخوارزميات،

بخصوص سؤالك العملية هي قياس عدد الخطوات على حسب حجم المدخلات للخوارزمية، امثلة:

بافتراض ان n هو عدد المدخلات (حجم المصفوفة التي سنرتبها مثلا)

x=1

هذه العملية ليست لها علاقة بالمدخلات لذلك فالوقت لها ثابت.

for i=1 to n

x=x+1

هذه العملية ستأخذ n خطوة

وهكذا

شيء اخر : عادة يتم تبسيط التعبير عند كتابة الBig O واخواتها ، مثلا لايوجد فرق بين كل من :

n

n-1000000

n+1000000

وهكذا

اي ان الثوابت يتم تجاهلها.

ولكن يوجد فرق كبير بين كل من :

n

n*n

2^n

وهكذا

بالتوفيق

اعذرونى على التدخل ... وكويس ان الموضوع اتفتح لان عندى استفسار بسيط

متى تطلع عدد العمليات n-1 ... الى ماذا يشير الواحد الصحيح ..؟

بافتراض ان n هو عدد المدخلات (حجم المصفوفة التي سنرتبها مثلا)

لو عدلنا في مدى التكرار في المثال السابق كالتالي:

for i=1 to n-1

x=x+1

العملية داخل التكرار ستأخذ n-1 خطوة

ارجو ان يكون الشرح واضح.

جزاك الله خيرا ...انا واخد بالى من ان اخر حاجه يوصلها الفور لوب يبقى هيا ديه عدد الخطوات .. بس مثلا فى الجورزم

for j=2 to length[A

do key....A[j

فى السطر الاول هيبقى عدد الخطوات n حيث اخر حاجه بتوصلها اللوب هيا عدد العناصر بتاعة المصفوفه A

اما فى السطر الثانى هيبقى عدد الخطوات ايه .؟ n ولا n-1

في السطر الاول n لانه في كل مرة سيتم اختبار الشرط هل تحقق ام لا

فسيكون لدينا خطوة اضافية زيادة عن عدد عناصر المصفوفة -1 عندها لن يتم تنفيذ العبارة في سطر 2

في السطر الثاني n-1 جرب بمثال بسيط لتتأكد مثلا مصفوفة ب 5 عناصر

ibr_exn كتب:

في السطر الاول n لانه في كل مرة سيتم اختبار الشرط هل تحقق ام لا

فسيكون لدينا خطوة اضافية زيادة عن عدد عناصر المصفوفة -1 عندها لن يتم تنفيذ العبارة في سطر 2

في السطر الثاني n-1 جرب بمثال بسيط لتتأكد مثلا مصفوفة ب 5 عناصر

جزاك الله خيرا :)