Python - เหตุผลของอัลกอริทึม

เพื่อให้การอ้างสิทธิ์เกี่ยวกับอัลกอริทึมมีประสิทธิภาพเราจำเป็นต้องมีเครื่องมือทางคณิตศาสตร์เพื่อพิสูจน์ เครื่องมือเหล่านี้ช่วยให้เราสามารถให้คำอธิบายที่น่าพอใจทางคณิตศาสตร์เกี่ยวกับประสิทธิภาพและความแม่นยำของอัลกอริทึม ด้านล่างนี้เป็นรายการของเครื่องมือทางคณิตศาสตร์บางส่วนที่สามารถใช้เพื่อพิสูจน์อัลกอริทึมหนึ่งเหนืออีกอันหนึ่งได้

• Direct Proof:

  เป็นการตรวจสอบคำสั่งโดยตรงโดยใช้การคำนวณโดยตรง ตัวอย่างเช่นผลรวมของเลขคู่สองตัวจะเป็นเลขคู่เสมอ ในกรณีนี้ให้เพิ่มตัวเลขสองตัวที่คุณกำลังตรวจสอบและตรวจสอบผลลัพธ์ว่าเป็นเลขคู่

• Proof by induction:

  ที่นี่เราเริ่มต้นด้วยตัวอย่างเฉพาะของความจริงจากนั้นสรุปให้เป็นค่าที่เป็นไปได้ทั้งหมดซึ่งเป็นส่วนหนึ่งของความจริง วิธีการนี้คือการพิจารณากรณีของความจริงที่ตรวจสอบแล้วพิสูจน์ว่าเป็นจริงสำหรับกรณีถัดไปสำหรับเงื่อนไขที่กำหนดเดียวกัน ตัวอย่างเช่นจำนวนบวกทั้งหมดของรูปแบบ 2n-1 เป็นเลขคี่ เราพิสูจน์ด้วยค่าที่แน่นอนของ n แล้วพิสูจน์ด้วยค่าถัดไปของ n สิ่งนี้สร้างคำสั่งให้เป็นจริงโดยการพิสูจน์การเหนี่ยวนำ

• Proof by contraposition:

  การพิสูจน์นี้ขึ้นอยู่กับเงื่อนไข If Not A หมายถึง Not B ดังนั้น A ก็หมายถึง B ตัวอย่างง่ายๆคือถ้ากำลังสองของ n เป็นค่า n ก็ต้องเป็นคู่ เพราะถ้ากำลังสองบน n ไม่ถึงแล้ว n จะไม่เป็นคู่

• Proof by exhaustion:

  สิ่งนี้คล้ายกับการพิสูจน์โดยตรง แต่ได้รับการจัดตั้งขึ้นโดยการเยี่ยมชมแต่ละกรณีแยกกันและพิสูจน์แต่ละกรณี ตัวอย่างของการพิสูจน์ดังกล่าวคือทฤษฎีบทสี่สี