คุณอาจเคยเจอสัญลักษณ์อย่าง O(log n) มากกว่าหนึ่งครั้งหรือได้ยินวลีเช่น “ความซับซ้อนในการคำนวณแบบลอการิทึม” ที่ส่งถึงอัลกอริธึมบางตัว และหากคุณยังไม่เข้าใจว่าสิ่งนี้หมายถึงอะไร บทความนี้เหมาะสำหรับคุณ

คะแนนความยาก

ความซับซ้อนของอัลกอริธึมมักจะวัดจากเวลาดำเนินการหรือการใช้หน่วยความจำ ในทั้งสองกรณี ความซับซ้อนขึ้นอยู่กับขนาดของข้อมูลอินพุต: อาร์เรย์ 100 องค์ประกอบจะถูกประมวลผลเร็วกว่าองค์ประกอบที่คล้ายกันใน 1,000 อย่างไรก็ตาม มีเพียงไม่กี่คนที่สนใจเวลาที่แน่นอน: ขึ้นอยู่กับโปรเซสเซอร์ ประเภทข้อมูล , ภาษาโปรแกรม และพารามิเตอร์อื่นๆ อีกมากมาย เฉพาะความซับซ้อนเชิงเส้นกำกับเท่านั้นที่สำคัญ เช่น ความซับซ้อนเมื่อขนาดของข้อมูลอินพุตมีแนวโน้มที่จะไม่มีที่สิ้นสุด

สมมติว่าอัลกอริทึมบางตัวจำเป็นต้องดำเนินการแบบมีเงื่อนไข 4n 3 + 7n เพื่อประมวลผลองค์ประกอบ n รายการของข้อมูลอินพุต เมื่อ n เพิ่มขึ้น เวลาทำงานสุดท้ายจะได้รับผลกระทบอย่างมากจากการเพิ่ม n ให้เป็นลูกบาศก์ มากกว่าการคูณด้วย 4 หรือบวก 7n จากนั้นพวกเขาบอกว่าความซับซ้อนของเวลาของอัลกอริธึมนี้คือ O (n 3) นั่นคือมันขึ้นอยู่กับขนาดของข้อมูลอินพุตเป็นลูกบาศก์

การใช้ตัวพิมพ์ใหญ่ O (หรือที่เรียกว่าสัญลักษณ์ O) มาจากคณิตศาสตร์ ซึ่งใช้เพื่อเปรียบเทียบพฤติกรรมเชิงเส้นกำกับของฟังก์ชัน อย่างเป็นทางการ O(f(n)) หมายความว่าเวลาทำงานของอัลกอริทึม (หรือจำนวนหน่วยความจำที่ใช้) จะเพิ่มขึ้นขึ้นอยู่กับขนาดของข้อมูลอินพุตไม่เร็วกว่าค่าคงที่บางตัวคูณด้วย f(n)

ตัวอย่าง

O(n) - ความซับซ้อนเชิงเส้น

ตัวอย่างเช่น อัลกอริธึมสำหรับการค้นหาองค์ประกอบที่ใหญ่ที่สุดในอาร์เรย์ที่ไม่ได้เรียงลำดับจะมีความซับซ้อนนี้ เราจะต้องผ่านองค์ประกอบทั้งหมด n รายการของอาร์เรย์เพื่อทำความเข้าใจว่าองค์ประกอบใดมีค่าสูงสุด

O(log n) - ความซับซ้อนของลอการิทึม

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

O(n 2) - ความซับซ้อนกำลังสอง

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

มีการให้คะแนนความยากอื่น ๆ แต่ทั้งหมดนั้นใช้หลักการเดียวกัน

นอกจากนี้ยังเกิดขึ้นว่าเวลาทำงานของอัลกอริทึมไม่ได้ขึ้นอยู่กับขนาดของข้อมูลอินพุตเลย จากนั้นความซับซ้อนจะแสดงเป็น O(1) . ตัวอย่างเช่น ในการกำหนดค่าขององค์ประกอบที่สามของอาร์เรย์ คุณไม่จำเป็นต้องจำองค์ประกอบหรืออ่านองค์ประกอบเหล่านั้นหลายครั้ง คุณเพียงแค่ต้องรอองค์ประกอบที่สามในสตรีมข้อมูลอินพุตเสมอ และนี่คือผลลัพธ์ ซึ่งจะใช้เวลาเท่ากันในการคำนวณจำนวนข้อมูลเท่าใดก็ได้

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

ความยากในการขุดคืออะไร? ใช้ Bitcoin เป็นตัวอย่าง

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

คำว่า “ความยากในการขุด” หมายถึงอะไร?

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

คุณสมบัติอย่างหนึ่งของสกุลเงินดิจิทัลคือลักษณะของภาวะเงินฝืด ซึ่งหมายความว่าจำนวนเหรียญที่ขุดได้ทั้งหมดต้องไม่เกินจำนวนที่ระบุในโค้ดโปรแกรม ตัวอย่างเช่น จำนวน Bitcoin สูงสุดคือ 21 ล้านเหรียญ ยิ่งไปกว่านั้น Bitcoin สุดท้ายจะถูกขุดในปี 2140 เท่านั้น แม้จะมีผู้ขุดจำนวนมาก แต่ก็มีการขุดเพียง 12.5 BTC ทุก ๆ 10 นาที เหรียญเหล่านี้จะถูกแจกจ่ายให้กับนักขุดตามพลังการประมวลผลที่ใช้ไป รางวัลสำหรับบล็อกที่เซ็นชื่อจะไม่เพิ่มขึ้น (และจะลดลงครึ่งหนึ่งทุกๆ 4 ปี) และหากจำนวนนักขุดเพิ่มขึ้น รายได้ของนักขุดแต่ละคนก็จะลดลงตามสัดส่วน ด้วยการมาถึงของนักขุด crypto หน้าใหม่มากขึ้น การแข่งขันเพื่อชิงรางวัลที่จำกัดก็เพิ่มมากขึ้น

เพื่อแสดงให้เห็นสถานการณ์นี้อย่างชัดเจน จึงได้มีการแนะนำพารามิเตอร์ที่คำนวณได้ของเครือข่ายสกุลเงินดิจิทัล “ความยากในการขุด” ความยากในการขุดเป็นตัวชี้วัดที่สะท้อนถึงความยากในการแก้ปัญหาทางคณิตศาสตร์เพื่อลงนามบล็อกและรับรางวัลจากบล็อกนั้น ความยากจะถูกคำนวณใหม่โดยอัตโนมัติหลังจากช่วงระยะเวลาหนึ่ง มันแตกต่างกันไปในแต่ละสกุลเงินดิจิทัล ตัวอย่างเช่น ความยากในการขุด Bitcoin จะถูกคำนวณใหม่ทุกๆ บล็อกในปี 2559 ซึ่งการขุดจะใช้เวลาประมาณ 2 สัปดาห์ ตามรหัสโปรแกรม ความยากจะถูกปรับเพื่อให้การค้นหาบล็อกถัดไปใช้เวลาประมาณ 10 นาที โดยไม่คำนึงถึงจำนวนผู้ขุดและแฮชเรตทั้งหมด

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

จะหาความยากในการขุดได้ที่ไหน ความยากในการขุด cryptocurrencies 10 อันดับแรก

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

ข้อมูลล่าสุดเกี่ยวกับสกุลเงินดิจิทัลมากกว่า 100 สกุลสามารถพบได้บนเว็บไซต์ต่อไปนี้:

• https://www.coinwarz.com/charts/difficulty-charts
• https://bitinfocharts.com/ru/

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

** สกุลเงินดิจิทัลบางสกุลไม่สามารถขุดได้ในความหมายดั้งเดิม บางคนใช้การขุด POS ซึ่งมีดอกเบี้ยเกิดขึ้นเป็นระยะ ๆ จากเหรียญในกระเป๋าเงิน สำหรับการขุด POS คุณไม่จำเป็นต้องซื้ออุปกรณ์พิเศษและเสียเงินกับค่าไฟฟ้า สกุลเงินดิจิทัลอื่น ๆ (เช่น Ripple) ได้ถูกขุดจนเต็มแล้ว และจะแจกจ่ายต่อระหว่างเจ้าของเท่านั้น

ความยากในการขุด: มีผลกระทบอะไรและทำไมมันถึงเติบโต

ความยากในการขุดจะกำหนดรายได้ของนักขุด จำนวนเหรียญที่ขุดได้จะแปรผกผันกับความยากในการขุด หากความยากของเครือข่ายเพิ่มขึ้น 20% รายได้สกุลเงินดิจิทัลของนักขุดแต่ละคนจะลดลง 20%

ตัวอย่างเช่น ASIC สำหรับการขุด bitcoin antminer s7 ในช่วงกลางปี ​​​​2560 (แม่นยำยิ่งขึ้นด้วยความยากลำบาก ณ วันที่ 1 กรกฎาคม 2017) ขุดได้ 0.06 BTC ต่อเดือน แต่ความซับซ้อนของเครือข่าย Bitcoin ก็เติบโตขึ้นอย่างต่อเนื่อง ตั้งแต่วันที่ 1 พฤศจิกายน 2017 อุปกรณ์เดียวกันนี้จะผลิตได้ 0.026 BTC ต่อเดือนแล้ว รายได้ของคนขุดแร่ลดลงมากกว่าครึ่งในเวลาเพียง 4 เดือน

แต่รายได้ที่ลดลงทุกสัปดาห์ก็ไม่ได้ทำให้การลงทุนในเหมืองมีความน่าสนใจน้อยลงแต่อย่างใด รายได้ในสกุลเงินดิจิทัลถูกชดเชยบางส่วนด้วยการเพิ่มขึ้นของอัตราแลกเปลี่ยนเป็นคำสั่ง ในตัวอย่างของเรา ในวันที่ 1 กรกฎาคม อัตรา Bitcoin อยู่ที่ 2,400 ดอลลาร์ และในวันที่ 1 พฤศจิกายน ราคาเพิ่มขึ้นเป็นเกือบ 6,700 ดอลลาร์ ปรากฎว่ารายได้ของนักขุดเหรียญ Fiat เพิ่มขึ้น แม้ว่าความซับซ้อนในการขุดจะเพิ่มขึ้นอย่างรวดเร็วก็ตาม

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

จากมุมมองทางเทคนิค ตัวบ่งชี้ความยากในการขุดขึ้นอยู่กับ:

• แฮชเรตเครือข่าย (จำนวนและพลังการคำนวณของอุปกรณ์ของนักขุดทั้งหมด)
• ความเร็วในการขุดบล็อกปี 2559

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

ความยากในการขุด Bitcoin

ความซับซ้อนที่เพิ่มขึ้นเกิดจากปัจจัยหลายประการที่มีความสัมพันธ์กันอย่างใกล้ชิด:

• การพัฒนาชิป ASIC และการเข้าสู่ตลาดโมเดลที่มีประสิทธิผลมากขึ้น
• การแพร่หลายของ Bitcoin และการไหลเข้าของนักขุดรายใหม่
• ผลตอบแทนจากการลงทุนในการขุดสูงเนื่องจากการเติบโตอย่างรวดเร็วของอัตราแลกเปลี่ยน Bitcoin เทียบกับดอลลาร์
• การถ่ายโอนพลังการประมวลผลจากสกุลเงินอื่นที่ราคาลดลงหรือเติบโตช้ากว่า Bitcoin
• ปัจจัยอื่นๆ

ความยากในการขุด Bitcoin เพิ่มขึ้น 5-6 เท่าตั้งแต่ปี 2559 การเติบโตยังคงดำเนินต่อไปเกือบจะไม่หยุดชะงัก เฉพาะเดือนสิงหาคม 2560 เป็นครั้งแรกในรอบปีที่มีดัชนีลดลง บางทีนี่อาจได้รับอิทธิพลจาก SegWit ของ Bitcoin ในเดือนสิงหาคม ซึ่งบังคับให้นักขุดบางรายโอนอำนาจไปยัง altcoins

6 คำตอบ

ความซับซ้อนจะถูกระบุเสมอโดยสัมพันธ์กับตัวแปรเฉพาะหรือชุดของตัวแปร ดังนั้นเมื่อมาตรฐานพูดถึงการแทรกเวลาคงที่ เรากำลังพูดถึงเวลาคงที่สัมพันธ์กับจำนวนองค์ประกอบในรายการ นั่นคือการแทรก O(1) หมายความว่าจำนวนองค์ประกอบที่มีอยู่ในรายการไม่ส่งผลกระทบต่อความซับซ้อนโดยรวมของการแทรก รายการสามารถมีองค์ประกอบได้ 500 หรือ 50000000 องค์ประกอบ และความซับซ้อนของการดำเนินการแทรกจะเหมือนกัน

ตัวอย่างเช่น std::list มีการแทรกและการลบ O(1) จำนวนองค์ประกอบในรายการไม่ได้ขึ้นอยู่กับความซับซ้อนของการแทรก อย่างไรก็ตามความซับซ้อนของการจัดสรรหน่วยความจำอาจขึ้นอยู่กับจำนวนของสิ่งต่าง ๆ ที่ได้รับการจัดสรรแล้ว แต่เนื่องจาก O(1) พูดถึงจำนวนองค์ประกอบในรายการ จึงไม่ครอบคลุมถึงเรื่องนั้น และนี่ไม่ถือว่าเกิดขึ้น เนื่องจากเราจะวัดความซับซ้อนของการจัดสรรหน่วยความจำ ไม่ใช่โครงสร้างข้อมูล

กล่าวโดยย่อ: นี่คืออีกมิติหนึ่ง

ซึ่งหมายความว่าเราสามารถใช้อัลกอริธึมของเราได้อย่างเต็มที่ตามที่เราต้องการ ซึ่งรวมถึงเวลาที่จริง ๆ แล้วเวลาไม่คงที่ในแง่เชิงปฏิบัติใดๆ แต่เมื่อเราเคารพจำนวน "การดำเนินการ" บนวัตถุที่มีอยู่

ไม่ได้ระบุความซับซ้อนที่เกี่ยวข้องกับการใช้งาน มีการระบุโดยสัมพันธ์กับอัลกอริธึม ไม่สำคัญว่าบริบทจะสามารถสลับได้เนื่องจากรันไทม์ไม่ใช่งานยาก

ดังที่กล่าวข้างต้น คุณสามารถใช้ std::list กับการจัดสรรหน่วยความจำที่เป็น O(log(n)) ที่เกี่ยวข้องกับการลบ (โดยที่ n คือจำนวนการจัดสรร) อย่างไรก็ตาม การลบองค์ประกอบในรายการจะยังคงเป็น O(1) เมื่อเทียบกับจำนวนองค์ประกอบในรายการ

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

ความซับซ้อนเป็นเครื่องมือในการประเมินประสิทธิภาพของอัลกอริทึม ความซับซ้อนไม่ได้หมายความว่าคุณสามารถหยุดคิดได้

"ค่าเสื่อมราคา" หมายถึงอะไรกันแน่?

ตามที่ฉันเข้าใจ ความซับซ้อนคงที่หมายความว่าการดำเนินการเป็น O(1) คุณสามารถบอกล่วงหน้าได้ว่าจะมีการดำเนินการอะตอมมิกจำนวนเท่าใด (อ่าน/เขียน คำแนะนำในการประกอบ หรืออะไรก็ตาม) และการประมาณนี้เป็นขอบเขตทั่วไปสำหรับสถานะที่เป็นไปได้ทั้งหมดของวัตถุเป้าหมาย สิ่งสำคัญคือ: ในสภาพแวดล้อมแบบมัลติเธรด คุณไม่สามารถคาดเดาโฟลว์สวิตช์ได้ ดังนั้นคุณจึงสามารถให้เหตุผลบางประการเกี่ยวกับเวลาทำงานที่ผ่านไปในระบบปฏิบัติการแบบเรียลไทม์เท่านั้น

เกี่ยวกับความซับซ้อนคงที่ที่ตัดจำหน่าย มันยิ่งอ่อนแอลง การเขียนสรุปคำตอบช่วยให้มั่นใจได้ว่า โดยเฉลี่ยแล้ว การปฏิบัติงานของคุณจะดำเนินไปอย่างต่อเนื่อง ซึ่งหมายความว่าจำนวนการดำเนินการเบื้องต้นสำหรับการดำเนินการภายหลัง N คือ O(N) ซึ่งหมายความว่าจำนวนการดำเนินการเบื้องต้นจะอยู่ที่ประมาณ O(1) แต่อนุญาตให้มีการกระโดดที่หายากบ้าง ตัวอย่างเช่น การเพิ่มองค์ประกอบที่ส่วนท้ายของเวกเตอร์มักจะเป็นแบบถาวร แต่บางครั้งจำเป็นต้องมีการยกของหนักเพิ่มเติม การมีเวลาคงที่ที่ตัดจำหน่ายหมายความว่าการดำเนินการพิเศษนั้นไม่ได้ดำเนินการบ่อยนักและต้องใช้เวลาที่คาดเดาได้ ดังนั้นเวลารวมของการดำเนินการ N ยังคงเป็น O(N) แน่นอนว่าการจับแบบเดียวกันนี้ใช้ที่นี่

ดังนั้นเพื่อตอบคำถามของคุณ:

• การรับประกันที่ซับซ้อนของมาตรฐานจะใช้กับจำนวนคำสั่งรหัสเครื่องที่จำเป็นสำหรับการดำเนินการเท่านั้น และไม่ได้หมายความว่าเวลาในการดำเนินการจะถูกจำกัดในทางใดทางหนึ่ง (อันที่จริง จนกระทั่งเมื่อเร็ว ๆ นี้ C++ ยังไม่มีตัวชี้หัวข้อที่เกี่ยวข้องกับภาษา ดังนั้นจากมุมมองของ C++ มาตรฐาน ในเวลานี้โปรแกรมจึงถูกดำเนินการบนเครื่อง C++ เฉพาะทาง)
• ค่าเสื่อมราคาจะ "จำกัดอยู่ที่ค่าเฉลี่ยคงที่" ซึ่งมักจะเกิดขึ้นในกรณีของเวลาดำเนินการที่จำกัดเกือบตลอดเวลาโดยมีการเบี่ยงเบนที่ค่อนข้างหายาก

แก้ไข:
คุณสามารถดูตัวอย่างมาตรา 23.1 ของมาตรฐาน C++:

ข้อกำหนดด้านความซับซ้อนทั้งหมดในส่วนนี้ระบุไว้ในแง่ของจำนวนการดำเนินการกับออบเจ็กต์ที่มีอยู่เท่านั้น

เมื่อการดำเนินการถูกกล่าวว่ามี "ความซับซ้อนคงที่" ก็มักจะหมายถึงความซับซ้อนของเวลาเป็นหลัก ฉันอาจหมายถึงความซับซ้อนเชิงพื้นที่ แต่ถ้าเป็นกรณีนี้ ก็จะมีการระบุอย่างชัดเจนตามปกติ

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

swap() เป็นความซับซ้อนคงที่ เพราะไม่ว่าเวกเตอร์จะมีองค์ประกอบกี่ตัวก็ตาม การดำเนินการจะใช้เวลาเท่ากัน

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

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

แต่การทำ push_back บนเวกเตอร์นั้นคาดเดาไม่ได้ยิ่งกว่า โดยส่วนใหญ่การดำเนินการนี้จะรวดเร็วมาก แต่ในบางครั้งจะต้องจัดสรรพื้นที่ใหม่สำหรับข้อมูลทั้งหมดและคัดลอกแต่ละองค์ประกอบไปยังตำแหน่งใหม่ ดังนั้นจึงคาดเดาได้น้อยกว่าในแง่ของเวลาดำเนินการมากกว่า list::push_front เพียงอย่างเดียว แต่ก็ยังเรียกว่าคงอยู่ (ตัดจำหน่าย) โดยเฉลี่ยแล้ว การเพิ่มข้อมูลจำนวนมากลงในเวกเตอร์จะมีความซับซ้อนที่ไม่ขึ้นอยู่กับจำนวนที่เพิ่มเข้าไป ซึ่งเป็นเหตุให้เรียกว่าเวลา "ค่าคงที่ตัดจำหน่าย" (ขวา?)

ความซับซ้อนคือ O(1) - ค่าคงที่ (โดยคำนึงถึงความซับซ้อนของเวลา) หมายความว่าเวลาที่อัลกอริธึมเสร็จสมบูรณ์ไม่เกี่ยวข้องกับขนาดของปัญหา

ดังนั้น การค้นหาค่าในโครงสร้างแฮชคือ O(1) เพราะเวลาที่ใช้ในการค้นหานั้นไม่ขึ้นกับจำนวนค่าของมัน อย่างไรก็ตาม สิ่งเดียวกันนี้ใช้ไม่ได้กับรายการที่เชื่อมโยงเนื่องจากเราต้องสแกนค่า (จำนวนที่เปลี่ยนแปลงเมื่อจำนวนองค์ประกอบเพิ่มขึ้น) เพื่อค้นหาค่าของเรา

ในกรณีที่ 3 เมื่อคัดลอกแต่ละองค์ประกอบ จะไม่ใช่การดำเนินการ O(1) แต่เป็นการดำเนินการ O(N) (แต่โดยส่วนใหญ่แล้วจะเป็นการดำเนินการ O(1) ดังนั้นจึงมักจะคงที่) การตัดจำหน่ายคำนึงถึงเรื่องนี้ด้วยการสังเกตว่าโดยปกติแล้วอัลกอริทึมจะเสร็จสิ้นภายในเวลา O(1) และไม่ค่อยตกอยู่ในกรณี O(N) นี้