In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform. Thus, the amount of time taken and the number of elementary operations performed by the algorithm are taken to be related by a constant factor.

Since an algorithm's running time may vary among different inputs of the same size, one commonly considers the worst-case time complexity, which is the maximum amount of time required for inputs of a given size. Less common, and usually specified explicitly, is the average-case complexity, which is the average of the time taken on inputs of a given size (this makes sense because there are only a finite number of possible inputs of a given size). In both cases, the time complexity is generally expressed as a function of the size of the input.^{[1]: 226} Since this function is generally difficult to compute exactly, and the running time for small inputs is usually not consequential, one commonly focuses on the behavior of the complexity when the input size increases—that is, the asymptotic behavior of the complexity. Therefore, the time complexity is commonly expressed using big O notation, typically ${\displaystyle O(n)}$,${\displaystyle O(n\log n)}$,${\displaystyle O(n^{\alpha })}$,${\displaystyle O(2^{n})}$, etc., where n is the size in units of bits needed to represent the input.

Algorithmic complexities are classified according to the type of function appearing in the big O notation. For example, an algorithm with time complexity ${\displaystyle O(n)}$ is a linear time algorithm and an algorithm with time complexity ${\displaystyle O(n^{\alpha })}$ for some constant ${\displaystyle \alpha >0}$ is a polynomial time algorithm.

The following table summarizes some classes of commonly encountered time complexities. In the table, poly(x) = x^O(1), i.e., polynomial in x.

Name	Complexity class	Time complexity (O(n))	Examples of running times	Example algorithms
constant time		${\displaystyle O(1)}$	10	การหาค่ามัธยฐานในอาร์เรย์ตัวเลขที่เรียงลำดับแล้ว การคำนวณ ( −1) n
เวลาแอคเคอร์แมนผกผัน		${\displaystyle O{\bigl (}\alpha (n){\bigr )}}$		เวลาเฉลี่ยต่อการดำเนินการโดยใช้เซตที่ไม่ซ้ำกัน
เวลาลอการิทึมแบบวนซ้ำ		${\displaystyle O(\log ^{*}n)}$		การระบายสีแบบกระจายของวงจร
ลอการิทึม-ลอการิทึม		${\displaystyle O(\log \log n)}$		เวลาเฉลี่ยต่อการดำเนินการโดยใช้คิวลำดับความสำคัญ แบบจำกัด [ 2 ]
เวลาลอการิทึม	ดล็อกไทม์	${\displaystyle O(\log n)}$	${\displaystyle \log n}$,${\displaystyle \log(n^{2})}$	การค้นหาแบบไบนารี
เวลาพหุลอการิทมิก		${\displaystyle {\textsf {poly}}(\log n)}$	${\displaystyle (\log n)^{2}}$
กำลังเศษส่วน		${\displaystyle O(n^{c})}$ที่ไหน${\displaystyle 0<c<1}$	${\displaystyle {\sqrt {n}}}$,${\displaystyle n^{\frac {2}{3}}}$	การค้นหาช่วงใน โครงสร้างต้นไม้ k -d
เวลาเชิงเส้น		${\displaystyle O(n)}$	n ,${\displaystyle 2n+5}$	การค้นหารายการที่เล็กที่สุดหรือใหญ่ที่สุดในอาร์เรย์ ที่ยัง ไม่ ได้เรียง ลำดับ อัลกอริทึมของคาดาเนะการค้นหาเชิงเส้น
เวลา "n log-star n"		${\displaystyle O(n\log ^{*}n)}$		อัลกอริทึม การสร้างสามเหลี่ยมจากรูปหลายเหลี่ยมของSeidel
เวลาเชิงเส้น		${\displaystyle O(n\log n)}$	${\displaystyle n\log n}$,${\displaystyle \log n!}$	การเรียงลำดับแบบเปรียบเทียบที่เร็วที่สุดการ แปลงฟูริเยร์ แบบ เร็ว
เวลากึ่งเชิงเส้น		${\displaystyle n{\textsf {poly}}(\log n)}$	${\displaystyle n\log ^{2}n}$	การประเมินพหุนามหลายจุด
เวลากำลังสอง		${\displaystyle O(n^{2})}$	${\displaystyle n^{2}}$	การเรียงลำดับแบบบับเบิลการเรียงลำดับแบบแทรก การเรียงลำดับ แบบคอนโวลูชันโดยตรง
เวลาลูกบาศก์		${\displaystyle O(n^{3})}$	${\displaystyle n^{3}}$	การคูณเมทริกซ์สองเมทริกซ์แบบง่ายๆ การคำนวณค่าสัมประสิทธิ์ สหสัมพันธ์บางส่วน${\displaystyle n\times n}$
เวลาพหุนาม	พี	${\displaystyle 2^{O(\log n)}={\textsf {poly}}(n)}$	${\displaystyle n^{2}+n}$,${\displaystyle n^{10}}$	อัลกอริทึมของ Karmarkarสำหรับ การ เขียนโปรแกรมเชิงเส้นการทดสอบความเป็นจำนวนเฉพาะ AKS [ 3 ] [ 4 ]
เวลากึ่งพหุนาม	คิวพี	${\displaystyle 2^{{\textsf {poly}}(\log n)}}$	${\displaystyle n^{\log \log n}}$,${\displaystyle n^{\log n}}$	อัลกอริทึมการประมาณค่าO (log 2 n )ที่รู้จักกันดีที่สุดสำหรับปัญหาต้นไม้ Steiner ที่มีทิศทาง ตัว แก้เกมพาริตีที่รู้จักกันดีที่สุด[ 5 ]อัลกอริ ทึมไอโซมอร์ฟิซึมกราฟที่รู้จักกันดีที่สุด
เวลาต่ำกว่าเลขชี้กำลัง(นิยามแรก)	SUBEXP	${\displaystyle O(2^{n^{\epsilon }})}$สำหรับทุกคน${\displaystyle \epsilon >0}$		ประกอบด้วยBPPเว้นแต่ EXPTIME (ดูด้านล่าง) จะเท่ากับ MA [ 6 ]
เวลาต่ำกว่าเลขชี้กำลัง(นิยามที่สอง)		${\displaystyle 2^{o(n)}}$	${\displaystyle 2^{\sqrt[{3}]{n}}}$	อัลกอริทึมคลาสสิกที่ดีที่สุดสำหรับการแยกตัวประกอบจำนวนเต็ม อัลกอริทึมที่ดีที่สุดเดิมสำหรับการหาความเหมือนกันของกราฟ
เวลาแบบเลขชี้กำลัง(ด้วยเลขชี้กำลังเชิงเส้น)	อี	${\displaystyle 2^{O(n)}}$	${\displaystyle 1.1^{n}}$,${\displaystyle 10^{n}}$	การแก้ปัญหาพนักงานขายเดินทางโดยใช้การเขียนโปรแกรมเชิงพลวัต
เวลาแฟกทอเรียล		${\displaystyle O(n)!=2^{O(n\log n)}}$	${\displaystyle n!,n^{n},2^{n\log n}}$	การแก้ปัญหาพนักงานขายเดินทางโดยใช้การค้นหาแบบบรูทฟอร์ซ
เวลาเลขชี้กำลัง	เวลาหมดอายุ	${\displaystyle 2^{{\textsf {poly}}(n)}}$	${\displaystyle 2^{n}}$,${\displaystyle 2^{n^{2}}}$	การแก้ปัญหาการคูณเมทริกซ์แบบลูกโซ่โดยใช้ การค้นหา แบบบรูทฟอร์ซการค้นหากลยุทธ์ที่ชนะในหมากรุกหมากฮอสหรือโกะโดยใช้กฎโคของญี่ปุ่นบนกระดาน ${\displaystyle n\times n}$
เวลาเลขชี้กำลังสองเท่า	2-EXPTIME	${\displaystyle 2^{2^{{\textsf {poly}}(n)}}}$	${\displaystyle 2^{2^{n}}}$	การตัดสินความจริงของข้อความที่กำหนดในเลขคณิตเพรสเบอร์เกอร์

อัลกอริทึมจะถูกเรียกว่าใช้เวลาคงที่ (มักแสดงด้วยสัญลักษณ์เวลา) เมื่อฟังก์ชันความซับซ้อนของมันถูกจำกัดด้วยค่าที่ไม่เปลี่ยนแปลงตามขนาดของข้อมูลนำเข้า ซึ่งหมายความว่าเวลาในการประมวลผลจะคงที่เสมอไม่ว่าจะประมวลผลข้อมูลมากน้อยเพียงใด ตัวอย่างเช่น การเข้าถึงองค์ประกอบเฉพาะในอาร์เรย์เป็นการดำเนินการที่ใช้เวลาคงที่ เนื่องจากต้องใช้การดำเนินการเพียงครั้งเดียวในการค้นหาองค์ประกอบนั้น ${\textstyle O(1)}$${\textstyle T(n)}$

ในทางตรงกันข้าม การหาค่าต่ำสุดในอาร์เรย์ที่ไม่มีลำดับนั้นไม่ใช่กระบวนการที่ใช้เวลาคงที่ เนื่องจากต้องตรวจสอบแต่ละองค์ประกอบทำให้มีความซับซ้อนของเวลาเชิงเส้น หรืออย่างไรก็ตาม หากทราบจำนวนองค์ประกอบและกำหนดไว้ตายตัว งานบางอย่างก็ยังสามารถพิจารณาได้ว่าใช้เวลาคงที่ ${\textstyle O(n)}$

ที่สำคัญ คำว่า "เวลาคงที่" ไม่ได้หมายความว่าเวลาในการทำงานจะต้องเป็นอิสระจากขนาดของปัญหาโดยสิ้นเชิง แต่หมายความว่าเวลาในการทำงานควรมีขอบเขตบนที่สม่ำเสมอโดยไม่ขึ้นอยู่กับขนาดของข้อมูลป้อนเข้า ตัวอย่างเช่น งานที่เกี่ยวข้องกับการสลับค่าของaและbเพื่อให้แน่ใจว่าเงื่อนไขเป็นไปตามที่กำหนด จะถูกจัดประเภทเป็นเวลาคงที่ แม้ว่าเวลาในการดำเนินการอาจแตกต่างกันไปขึ้นอยู่กับว่าเงื่อนไขนั้นเป็นไปตามที่กำหนดแล้วหรือไม่ กุญแจสำคัญคือต้องมีค่าคงที่t อยู่ค่าหนึ่ง ซึ่งเวลาที่ใช้จะไม่เกินt เสมอ ไม่ว่าค่าของข้อมูลป้อนเข้า จะเป็นเท่าใดก็ตาม${\textstyle a\leq b}$

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

กล่าวกันว่าอัลกอริทึมใช้เวลาแบบลอการิทึมเมื่อเนื่องจากและมีความสัมพันธ์กันด้วยตัวคูณคงที่และตัวคูณดังกล่าวไม่เกี่ยวข้องกับการจำแนกประเภทบิ๊กโอ ดังนั้นการใช้งานมาตรฐานสำหรับอัลกอริทึมที่ใช้เวลาแบบลอการิทึมจึงไม่ขึ้นอยู่กับฐานของลอการิทึมที่ปรากฏในนิพจน์ของ T${\displaystyle T(n)=O(\log n)}$${\displaystyle \log _{a}n}$${\displaystyle \log _{b}n}$${\displaystyle O(\log n)}$

อัลกอริทึมที่ใช้เวลาในระดับลอการิทึมมักพบได้ในการดำเนินการกับต้นไม้ไบนารีหรือเมื่อใช้การค้นหาแบบไบนารี

อัลกอริทึมจะถือว่ามีประสิทธิภาพสูง หากอัตราส่วนของจำนวนการดำเนินการต่อขนาดของข้อมูลนำเข้าลดลงและมีแนวโน้มเข้าใกล้ศูนย์เมื่อn เพิ่มขึ้น อัลกอริทึมที่ต้องเข้าถึงองค์ประกอบทั้งหมดของข้อมูลนำเข้าจะไม่สามารถใช้เวลาในระดับลอการิทึมได้ เนื่องจากเวลาที่ใช้ในการ อ่าน ข้อมูลนำเข้าขนาดnจะอยู่ในระดับเดียวกับn²${\displaystyle O(\log n)}$

ตัวอย่างของเวลาแบบลอการิทึมคือการค้นหาในพจนานุกรม พิจารณาพจนานุกรมDที่มี รายการ nรายการ เรียงตามลำดับตัวอักษรเราสมมติว่า สำหรับn > 0 เราสามารถเข้าถึง รายการที่ kของพจนานุกรมได้ในเวลาคงที่ ให้แทน รายการที่ k นี้ ภายใต้สมมติฐานเหล่านี้ การทดสอบว่าคำwอยู่ในพจนานุกรมหรือไม่ สามารถทำได้ในเวลาแบบลอการิทึม: พิจารณาโดยที่แทนฟังก์ชันปัดเศษ ลง ถ้า—นั่นคือ คำwอยู่ตรงกลางของพจนานุกรมพอดี—เราก็เสร็จสิ้น มิฉะนั้น ถ้า—นั่นคือ ถ้าคำwมาก่อนคำตรงกลางในลำดับตัวอักษรของพจนานุกรมทั้งหมด—เราจะค้นหาต่อไปในลักษณะเดียวกันในครึ่งซ้าย (นั่นคือ ครึ่งก่อนหน้า) ของพจนานุกรม และทำซ้ำเช่นนี้ไปเรื่อยๆ จนกว่าจะพบคำที่ถูกต้อง มิฉะนั้น ถ้าคำ w อยู่หลังคำตรงกลาง ให้ดำเนินการในทำนองเดียวกันกับครึ่งขวาของพจนานุกรม อัลกอริทึมนี้คล้ายกับวิธีการที่มักใช้ในการค้นหารายการในพจนานุกรมกระดาษ ดังนั้น พื้นที่การค้นหาภายในพจนานุกรมจึงลดลงเมื่ออัลกอริทึมเข้าใกล้คำเป้าหมายมากขึ้น ${\displaystyle 1\leq k\leq n}$${\displaystyle D(k)}$${\displaystyle D\left(\left\lfloor {\frac {n}{2}}\right\rfloor \right)}$${\displaystyle \lfloor \;\rfloor }$${\displaystyle w=D\left(\left\lfloor {\frac {n}{2}}\right\rfloor \right)}$${\displaystyle w<D\left(\left\lfloor {\frac {n}{2}}\right\rfloor \right)}$

กล่าวกันว่าอัลกอริทึมทำงานในเวลาพหุโลการิทึมถ้าเวลาของอัลกอริทึมนั้นคือสำหรับค่าคงที่k บางค่า อีกวิธีหนึ่งในการเขียนคือ ${\displaystyle T(n)}$${\displaystyle O{\bigl (}(\log n)^{k}{\bigr )}}$${\displaystyle O(\log ^{k}n)}$

ตัวอย่างเช่นการเรียงลำดับโซ่เมทริกซ์สามารถแก้ไขได้ในเวลาพหุลอการิทึมบนเครื่องเข้าถึงแบบสุ่มขนาน [ ^{7 ]}และกราฟสามารถกำหนดให้เป็นระนาบได้^ในลักษณะไดนามิกอย่างสมบูรณ์ในเวลาต่อการดำเนินการแทรก/ลบ^{[ 8 ]}${\displaystyle O(\log ^{3}n)}$

กล่าวได้ว่าอัลกอริทึมทำงานในเวลาต่ำกว่าเชิงเส้น ( sub- linear time ) ถ้าโดยเฉพาะอย่างยิ่ง อัลกอริทึมที่มีความซับซ้อนเชิงเวลาตามที่กำหนดไว้ข้างต้นนั้นจะต้อง ทำงานในเวลาต่ำกว่าเชิงเส้น${\displaystyle T(n)=o(n)}$

คำว่าอัลกอริทึมเวลาแบบซับลิเนียร์โดยเฉพาะมักหมายถึงอัลกอริทึมแบบสุ่มที่สุ่มตัวอย่างเศษส่วนเล็ก ๆ ของอินพุตและประมวลผลอย่างมีประสิทธิภาพเพื่ออนุมานคุณสมบัติของอินสแตนซ์ทั้งหมดโดยประมาณ^{[ 9 ]} อัลกอริทึมเวลาแบบซับลิเนีย ร์ ประเภทนี้มีความเกี่ยวข้องอย่างใกล้ชิดกับการทดสอบคุณสมบัติและสถิติ

สถานการณ์อื่นๆ ที่อัลกอริธึมสามารถทำงานได้ในเวลาต่ำกว่าเชิงเส้น ได้แก่:

• อัลกอริทึมแบบขนานที่มีปริมาณงาน รวมเชิงเส้นหรือมากกว่า (ทำให้สามารถอ่านข้อมูลอินพุตทั้งหมดได้) แต่มีความลึก ต่ำกว่า เชิง เส้น
• อัลกอริทึมที่มีข้อสมมติฐานที่รับประกันได้เกี่ยวกับโครงสร้างของข้อมูลป้อนเข้า ตัวอย่างที่สำคัญคือการดำเนินการกับโครงสร้างข้อมูลเช่นการค้นหาแบบไบนารีในอาร์เรย์ที่เรียงลำดับแล้ว
• อัลกอริทึมที่ค้นหาโครงสร้างเฉพาะที่ในอินพุต เช่น การค้นหาค่าต่ำสุดเฉพาะที่ในอาร์เรย์ 1 มิติ (สามารถแก้ไขได้ใน  เวลาโดยใช้การค้นหาแบบไบนารีรูปแบบหนึ่ง) แนวคิดที่เกี่ยวข้องอย่างใกล้ชิดคืออัลกอริทึมการคำนวณเฉพาะที่ (LCA)ซึ่งอัลกอริทึมจะรับอินพุตขนาดใหญ่และสอบถามข้อมูลเฉพาะที่เกี่ยวกับเอาต์พุตขนาดใหญ่ที่ถูกต้อง^{[ 10 ]}${\displaystyle O(\log(n))}$

กล่าวกันว่าอัลกอริทึมใช้เวลาเชิงเส้นหรือเวลาเชิงเส้น ถ้าความซับซ้อนเชิงเวลาของมันคือσ² โดยทั่วไปแล้ว หมายความว่าเวลาในการทำงานจะเพิ่มขึ้นอย่างมากที่สุดเป็นเชิงเส้นตามขนาดของข้อมูลนำเข้า กล่าวให้แม่นยำยิ่งขึ้น หมายความว่ามีค่าคงที่cที่ทำให้เวลาในการทำงานมีค่าไม่เกิน σ² สำหรับทุกข้อมูลนำเข้าที่มีขนาดnตัวอย่างเช่น ขั้นตอนการบวกองค์ประกอบทั้งหมดของลิสต์ต้องใช้เวลาแปรผันตรงกับความยาวของลิสต์ ถ้าเวลาในการบวกมีค่าคงที่ หรืออย่างน้อยก็ถูกจำกัดด้วยค่าคงที่ ${\displaystyle O(n)}$${\displaystyle O(n)}$${\displaystyle cn}$

เวลาเชิงเส้น (Linear time) คือความซับซ้อนของเวลาที่ดีที่สุดเท่าที่จะเป็นไปได้ในสถานการณ์ที่อัลกอริทึมต้องอ่านข้อมูลเข้าทั้งหมดตามลำดับ ดังนั้นจึงมีการวิจัยมากมายที่มุ่งเน้นไปที่การค้นหาอัลกอริทึมที่มีเวลาเชิงเส้น หรืออย่างน้อยก็ใกล้เคียงกับเวลาเชิงเส้น การวิจัยนี้รวมถึงวิธีการทั้งด้านซอฟต์แวร์และฮาร์ดแวร์ มีเทคโนโลยีฮาร์ดแวร์หลายอย่างที่ใช้ประโยชน์จากความขนานเพื่อให้ได้ผลลัพธ์นี้ ตัวอย่างเช่นหน่วยความจำที่สามารถระบุตำแหน่งตามเนื้อหา (Content-addressable memory ) แนวคิดเรื่องเวลาเชิงเส้นนี้ถูกนำมาใช้ในอัลกอริทึมการจับคู่สตริง เช่น อัลกอริทึมการค้นหาสตริง ของ Boyer–Mooreและอัลกอริทึมของ Ukkonen

กล่าวกันว่าอัลกอริทึมทำงานในเวลากึ่งเชิงเส้น (เรียกอีกอย่างว่าเวลาลอการิทึมเชิงเส้น ) ถ้า สำหรับค่าคงที่บวก kบางค่า[ ^{11 ]}เวลาเชิงเส้นคือกรณี^{[ 12 ]}โดยใช้สัญกรณ์ O แบบอ่อน อัลกอริ^ทึมเหล่านี้คืออัลกอริทึมเวลากึ่งเชิงเส้นยังเป็นสำหรับค่าคงที่ทุกค่า และดังนั้นจึงทำงานได้เร็วกว่าอัลกอริทึมเวลาพหุนามใด ๆที่ขอบเขตเวลารวมถึงพจน์สำหรับค่าคงที่ใดๆ ${\displaystyle T(n)=O(n\log ^{k}n)}$${\displaystyle k=1}$${\displaystyle {\tilde {O}}(n)}$${\displaystyle O(n^{1+\varepsilon })}$${\displaystyle \varepsilon >0}$${\displaystyle n^{c}}$${\displaystyle c>1}$

อัลกอริทึมที่ทำงานในเวลาแบบกึ่งเชิงเส้น ได้แก่:

• การเรียงลำดับแบบผสานในตำแหน่งเดิม ( In-place merge sort)${\displaystyle O(n\log ^{2}n)}$
• อัลกอริ ทึมQuickSortในเวอร์ชันแบบสุ่ม มีเวลาการทำงานโดยเฉลี่ยเมื่อพิจารณาจากกรณีที่เลวร้ายที่สุด ส่วนเวอร์ชันที่ไม่ใช้การสุ่ม มีเวลาการทำงานเมื่อพิจารณาจากความซับซ้อนโดยเฉลี่ยเท่านั้น${\displaystyle O(n\log n)}$${\displaystyle O(n\log n)}$${\displaystyle O(n\log n)}$
• ฮีปซอร์ต , เมอร์จซอร์ต, อินโทรซอร์ต , ไบนารีทรีซอร์ต, สมูทซอร์ต , แพตตี้ซอร์ตติ้งฯลฯ ในกรณีที่เลวร้ายที่สุด${\displaystyle O(n\log n)}$
• การแปลงฟูริเยร์แบบเร็ว${\displaystyle O(n\log n)}$
• การคำนวณอาร์เรย์ Monge${\displaystyle O(n\log n)}$
• อัลกอริทึมSchönhage–Strassenสำหรับการคูณ${\displaystyle O(n\log n\log \log n)}$

ในหลายกรณีเวลาในการทำงานเป็นเพียงผลลัพธ์ของการดำเนินการซ้ำnครั้ง (สำหรับสัญลักษณ์ โปรดดูสัญลักษณ์ Big O § ตระกูลสัญลักษณ์ Bachmann–Landau ) ตัวอย่างเช่นการเรียงลำดับแบบต้นไม้ไบนารีสร้างต้นไม้ไบนารีโดยการแทรกแต่ละองค์ประกอบของ อาร์เรย์ขนาด nทีละรายการ เนื่องจากการดำเนินการแทรกในต้นไม้ค้นหาไบนารีแบบปรับสมดุลตัวเองใช้เวลา ดังนั้นอัลกอริทึมทั้งหมดจึงใช้เวลา ${\displaystyle O(n\log n)}$${\displaystyle \Theta (\log n)}$${\displaystyle O(\log n)}$${\displaystyle O(n\log n)}$

การเรียงลำดับแบบเปรียบเทียบต้องใช้การเปรียบเทียบอย่างน้อยในกรณีที่เลวร้ายที่สุด เนื่องจากตามการประมาณของสเตอร์ลิงนอกจากนี้ยังมักเกิดขึ้นจากความสัมพันธ์เวียนเกิดด้วย ${\displaystyle \Omega (n\log n)}$${\displaystyle \log(n!)=\Theta (n\log n)}$${\textstyle T(n)=2T\left({\frac {n}{2}}\right)+O(n)}$

กล่าวได้ว่าอัลกอริทึมมีเวลาการทำงานต่ำกว่ากำลังสองถ้า. ${\displaystyle T(n)=o(n^{2})}$

ตัวอย่างเช่น อัลก อริทึมการเรียงลำดับ แบบง่ายๆ ที่ใช้การเปรียบเทียบ นั้นใช้เวลาประมวลผลระดับกำลังสอง (เช่น การเรียงลำดับแบบแทรก ) แต่ก็มีอัลกอริทึมขั้นสูงกว่าที่ใช้เวลาประมวลผลต่ำกว่ากำลังสอง (เช่นการเรียงลำดับแบบเชลล์ ) ไม่มีอัลกอริทึมการเรียงลำดับทั่วไปใดที่ใช้เวลาประมวลผลเชิงเส้น แต่การเปลี่ยนแปลงจากระดับกำลังสองไปเป็นระดับต่ำกว่ากำลังสองนั้นมีความสำคัญอย่างยิ่งในทางปฏิบัติ

กล่าวกันว่าอัลกอริทึมมีเวลาพหุนามหากเวลาการทำงานของอัลกอริทึมนั้นมี^{ขอบเขต}บนโดย นิพจน์ พหุนามในขนาดของอินพุตสำหรับอัลกอริทึม นั่นคือT ( n ) = O ( nk ) สำหรับค่าคงที่ บวกkบางค่า^{[ 1 ] [ 13 ]}ปัญหาที่มีอัลกอริทึมเวลาพหุนามแบบกำหนดได้นั้นจัดอยู่ในชั้นความซับซ้อนPซึ่งเป็นศูนย์กลางในสาขาทฤษฎีความซับซ้อนของการคำนวณวิทยานิพนธ์ของ Cobhamระบุว่าเวลาพหุนามเป็นคำพ้องความหมายของ "จัดการได้" "เป็นไปได้" "มีประสิทธิภาพ" หรือ "เร็ว" ^{[ 14 ]}

ตัวอย่างของอัลกอริธึมที่ทำงานในเวลาพหุนาม:

• อั ลกอริทึมการเรียงลำดับ แบบ Selection Sortบน จำนวนเต็ม nตัว จะทำการคำนวณโดยใช้ค่าคงที่A บางค่า ดังนั้นจึงใช้เวลาและเป็นอัลกอริทึมแบบเวลาพหุนาม${\displaystyle An^{2}}$${\displaystyle O(n^{2})}$
• การคำนวณทางคณิตศาสตร์พื้นฐานทั้งหมด (การบวก การลบ การคูณ การหาร และการเปรียบเทียบ) สามารถทำได้ในเวลาพหุนาม
• การจับคู่สูงสุดในกราฟสามารถทำได้ในเวลาพหุนาม ในบางบริบท โดยเฉพาะอย่างยิ่งในการเพิ่มประสิทธิภาพจะมีการแยกแยะระหว่าง อัลกอริทึม ที่ใช้เวลาพหุนามอย่างเข้มงวดและอัลกอริทึมที่ใช้เวลาพหุนามอย่างอ่อน

แนวคิดทั้งสองนี้จะมีความเกี่ยวข้องก็ต่อเมื่อข้อมูลที่ป้อนเข้าสู่อัลกอริทึมประกอบด้วยจำนวนเต็มเท่านั้น

แนวคิดเรื่องเวลาพหุนามนำไปสู่ระดับความซับซ้อนหลายระดับในทฤษฎีความซับซ้อนของการคำนวณ ระดับความซับซ้อนที่สำคัญบางระดับที่กำหนดโดยใช้เวลาพหุนามมีดังต่อไปนี้

• P :ระดับความซับซ้อนของปัญหาการตัดสินใจที่สามารถแก้ไขได้บนเครื่องทัวริงแบบกำหนดได้ในเวลาพหุนาม
• NP : ระดับความซับซ้อนของปัญหาการตัดสินใจที่สามารถแก้ไขได้บนเครื่องทัวริงแบบไม่กำหนด (non-deterministic Turing machine)ในเวลาพหุนาม (polynomial time)
• ZPP : ระดับความซับซ้อนของปัญหาการตัดสินใจที่สามารถแก้ไขได้โดยไม่มีข้อผิดพลาดบนเครื่องทัวริงเชิงความน่าจะเป็นในเวลาพหุนาม
• RP : ระดับความซับซ้อนของปัญหาการตัดสินใจที่สามารถแก้ไขได้โดยมีข้อผิดพลาดด้านเดียวบนเครื่องทัวริงเชิงความน่าจะเป็นในเวลาพหุนาม
• BPP : ระดับความซับซ้อนของปัญหาการตัดสินใจที่สามารถแก้ไขได้โดยมีข้อผิดพลาดสองด้านบนเครื่องทัวริงเชิงความน่าจะเป็นในเวลาพหุนาม
• BQP : ระดับความซับซ้อนของปัญหาการตัดสินใจที่สามารถแก้ไขได้ด้วยข้อผิดพลาดสองด้านบนเครื่องทัวริงควอนตัมในเวลาพหุนาม

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

อัลกอริทึมจะถูกกำหนดให้ใช้เวลา ซูเปอร์พหุนามหากT ( n ) ไม่ถูกจำกัดค่าบนด้วยพหุนามใดๆ กล่าวคือ ถ้าสำหรับจำนวนเต็ม บวก ${\displaystyle T(n)\not \in O(n^{c})}$cทุกตัว

ตัวอย่างเช่น อัลกอริทึมที่ใช้เวลา2nขั้นตอนในการประมวลผลข้อมูลขนาดn จะต้อง ^ใช้เวลามากกว่าพหุนาม (หรือเวลาแบบเลขชี้กำลัง)

อัลกอริทึมที่ใช้ทรัพยากรแบบเลขชี้กำลังนั้นเห็นได้ชัดว่าเป็นซูเปอร์พหุนาม แต่บางอัลกอริทึมก็เป็นซูเปอร์พหุนามที่อ่อนมากเท่านั้น ตัวอย่างเช่นการทดสอบความเป็นจำนวนเฉพาะของ Adleman–Pomerance–Rumelyใช้ เวลา n ^{O (log log n )}ในการ ประมวลผลข้อมูลอินพุต n บิต ซึ่งเติบโตเร็วกว่าพหุนามใดๆ สำหรับ nที่มากพอแต่ขนาดของข้อมูลอินพุตจะต้องมีขนาดใหญ่จนไม่สามารถใช้งานได้จริงก่อนที่จะไม่สามารถถูกครอบงำโดยพหุนามที่มีดีกรีน้อยได้

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

อัลกอริ ทึมเวลาควาซีพหุนาม (Quasi-polynomial time algorithms) คืออัลกอริทึมที่มีเวลาการทำงานแสดงการเติบโตแบบควาซีพหุนามซึ่งเป็นพฤติกรรมที่อาจช้ากว่าเวลาพหุนาม แต่เร็วกว่าเวลาเลขชี้กำลัง อย่างมาก เวลาการทำงานในกรณีที่เลวร้ายที่สุดของอัลกอริทึมเวลาควาซีพหุนามคือสำหรับค่าคงที่บางค่าเมื่อค่านี้จะให้เวลาพหุนาม และเมื่อค่านี้จะให้เวลาต่ำกว่าเชิงเส้น (sub-linear time) ${\displaystyle 2^{O(\log ^{c}n)}}$${\displaystyle c>0}$${\displaystyle c=1}$${\displaystyle c<1}$

มีปัญหาบางอย่างที่เราทราบว่ามีอัลกอริทึมที่ใช้เวลาทำงานแบบกึ่งพหุนาม แต่ยังไม่มีอัลกอริทึมที่ใช้เวลาทำงานแบบพหุนาม ปัญหาเหล่านี้เกิดขึ้นในอัลกอริทึมการประมาณค่า ตัวอย่างที่มีชื่อเสียงคือปัญหาต้นไม้สไตเนอร์ แบบมีทิศทาง ซึ่งมีอัลกอริทึมการประมาณค่าที่ใช้เวลาทำงานแบบกึ่งพหุนาม โดยได้ค่าประมาณเท่ากับ( โดยที่ nคือจำนวนจุดยอด) แต่การพิสูจน์ว่ามีอัลกอริทึมที่ใช้เวลาทำงานแบบพหุนามดังกล่าวอยู่จริงนั้นยังคงเป็นปัญหาที่ยังไม่มีคำตอบ ${\displaystyle O(\log ^{3}n)}$

ปัญหาการคำนวณอื่นๆ ที่มีวิธีแก้ปัญหาแบบกึ่งพหุนามแต่ไม่มีวิธีแก้ปัญหาแบบพหุนามที่ทราบ ได้แก่ ปัญหา คลิกที่ถูกปลูกฝังซึ่งเป้าหมายคือการค้นหาคลิกขนาดใหญ่ในการรวมกันของคลิกและกราฟสุ่มแม้ว่าจะสามารถแก้ได้แบบกึ่งพหุนาม แต่ก็มีการคาดเดาว่าปัญหาคลิกที่ถูกปลูกฝังไม่มีวิธีแก้ปัญหาแบบพหุนาม การคาดเดาเรื่องคลิกที่ถูกปลูกฝังนี้ถูกนำมาใช้เป็นสมมติฐานความยากในการคำนวณเพื่อพิสูจน์ความยากของปัญหาอื่นๆ อีกหลายปัญหาในทฤษฎีเกม เชิง คำนวณการทดสอบคุณสมบัติและ การเรียน รู้ของเครื่อง^{[ 15 ]}

คลาสความซับซ้อนQPประกอบด้วยปัญหาทั้งหมดที่มีอัลกอริทึมเวลากึ่งพหุนาม สามารถกำหนดได้ในแง่ของDTIMEดังต่อไปนี้^{[ 16 ]}

${\displaystyle {\mbox{QP}}=\bigcup _{c\in \mathbb {N} }{\mbox{DTIME}}\left(2^{\log ^{c}n}\right)}$

ในทฤษฎีความซับซ้อน ปัญหา P เทียบกับ NP ที่ยังแก้ไม่ตก นั้นถามว่า ปัญหาทั้งหมดใน NP มีอัลกอริทึมที่ใช้เวลาแบบพหุนามหรือไม่ อัลกอริทึมที่เป็นที่รู้จักดีที่สุดสำหรับ ปัญหา NP-completeเช่น 3SAT เป็นต้น ใช้เวลาแบบเลขชี้กำลัง อันที่จริง มีการตั้งข้อสันนิษฐานสำหรับปัญหา NP-complete ตามธรรมชาติหลายปัญหาว่าไม่มีอัลกอริทึมที่ใช้เวลาต่ำกว่าเลขชี้กำลัง ในที่นี้ "เวลาต่ำกว่าเลขชี้กำลัง" หมายถึงความหมายที่สองที่นำเสนอไว้ด้านล่าง (ในทางกลับกัน ปัญหาเกี่ยวกับกราฟหลายปัญหาที่แสดงในรูปแบบธรรมชาติโดยเมทริกซ์ประชิดสามารถแก้ไขได้ในเวลาต่ำกว่าเลขชี้กำลังเพียงเพราะขนาดของข้อมูลนำเข้าเป็นกำลังสองของจำนวนจุดยอด) ข้อสันนิษฐานนี้ (สำหรับปัญหา k-SAT) เรียกว่าสมมติฐานเวลาแบบเลขชี้กำลัง^{[ 17 ]}เนื่องจากมีการคาดเดาว่าปัญหา NP-complete ไม่มีอัลกอริทึมเวลาแบบกึ่งพหุนาม ผลลัพธ์ที่ไม่สามารถประมาณค่าได้บางส่วนในสาขาอัลกอริทึมการประมาณค่าจึงตั้งสมมติฐานว่าปัญหา NP-complete ไม่มีอัลกอริทึมเวลาแบบกึ่งพหุนาม ตัวอย่างเช่น ดูผลลัพธ์ที่ไม่สามารถประมาณค่าได้ที่ทราบสำหรับปัญหา การครอบคลุมเซต

คำว่าเวลาต่ำกว่าเลขชี้กำลังใช้เพื่อแสดงว่าเวลาการทำงานของอัลกอริทึมบางอย่างอาจเติบโตเร็วกว่าพหุนามใดๆ แต่ยังคงน้อยกว่าเลขชี้กำลังอย่างมีนัยสำคัญ ในแง่นี้ ปัญหาที่มีอัลกอริทึมเวลาต่ำกว่าเลขชี้กำลังจึงจัดการได้ง่ายกว่าปัญหาที่มีเฉพาะอัลกอริทึมเลขชี้กำลังเท่านั้น คำจำกัดความที่แน่นอนของ "ต่ำกว่าเลขชี้กำลัง" ยังไม่เป็นที่ยอมรับโดยทั่วไป^{[ 18 ]}อย่างไรก็ตาม คำจำกัดความที่ใช้กันอย่างแพร่หลายที่สุดสองคำมีดังต่อไปนี้

กล่าวได้ว่าปัญหาสามารถแก้ไขได้ในเวลาต่ำกว่าเลขชี้กำลัง หากสามารถแก้ไขได้ในเวลาการทำงานซึ่งลอการิทึมเติบโตน้อยกว่าพหุนามใดๆ ที่กำหนดไว้ กล่าวให้แม่นยำยิ่งขึ้น ปัญหาจะอยู่ในเวลาต่ำกว่าเลขชี้กำลัง หากสำหรับทุกε > 0จะมีอัลกอริทึมที่แก้ปัญหาได้ในเวลาO (2 ^{n ε} ) เซตของปัญหาทั้งหมดดังกล่าวคือคลาสความซับซ้อนSUBEXPซึ่งสามารถกำหนดได้ในแง่ของDTIMEดังต่อไปนี้^{[ 6 ] [ 19 ] [ 20 ] [ 21 ]}

${\displaystyle {\textsf {SUBEXP}}=\bigcap _{\varepsilon >0}{\textsf {DTIME}}\left(2^{n^{\varepsilon }}\right)}$

แนวคิดเรื่องค่าต่ำกว่าเลขชี้กำลังนี้ไม่สม่ำเสมอในแง่ของεในแง่ที่ว่าεไม่ใช่ส่วนหนึ่งของข้อมูลนำเข้า และแต่ละ ε อาจมีอัลกอริทึมของตนเองสำหรับปัญหาดังกล่าว

ผู้เขียนบางคนกำหนดเวลาต่ำกว่าเลขชี้กำลังเป็นเวลาการทำงานใน. ^{[ 17 ] [ 22 ] [ 23 ]}คำจำกัดความนี้อนุญาตให้มีเวลาการทำงานที่มากกว่าคำจำกัดความแรกของเวลาต่ำกว่าเลขชี้กำลัง ตัวอย่างของอัลกอริทึมที่มีเวลาต่ำกว่าเลขชี้กำลังดังกล่าวคืออัลกอริทึมคลาสสิกที่รู้จักกันดีที่สุดสำหรับการแยกตัวประกอบจำนวนเต็ม นั่นคือตะแกรงฟิลด์จำนวนทั่วไปซึ่งทำงานในเวลาประมาณโดยที่ความยาวของอินพุตคือnอีกตัวอย่างหนึ่งคือปัญหาความเหมือนกันของกราฟซึ่งอัลกอริทึมที่รู้จักกันดีที่สุดตั้งแต่ปี 1982 ถึง 2016 แก้ได้ในอย่างไรก็ตามในงาน STOC 2016 ได้มีการนำเสนออัลกอริทึมที่มีเวลาแบบกึ่งพหุนาม^{[ 24 ]}${\displaystyle 2^{o(n)}}$${\displaystyle 2^{{O}(n^{1/3}(\log n)^{2/3})}}$${\displaystyle 2^{O\left({\sqrt {n\log n}}\right)}}$

ความแตกต่างอยู่ที่ว่าอัลกอริทึมได้รับอนุญาตให้เป็นแบบย่อยเลขชี้กำลังในขนาดของอินสแตนซ์ จำนวนจุดยอด หรือจำนวนขอบ ในความซับซ้อนแบบพารามิเตอร์ความแตกต่างนี้จะถูกทำให้ชัดเจนโดยการพิจารณาคู่ของปัญหาการตัดสินใจและพารามิเตอร์ k SUBEPTคือคลาสของปัญหาพารามิเตอร์ทั้งหมดที่ทำงานในเวลาแบบย่อยเลขชี้กำลังในkและแบบพหุนามในขนาดอินพุตn : ^{[ 25 ]}${\displaystyle (L,k)}$

${\displaystyle {\textsf {SUBEPT}}={\textsf {DTIME}}\left(2^{o(k)}\cdot {\textsf {poly}}(n)\right).}$

กล่าวโดยละเอียดแล้ว SUBEPT คือกลุ่มของปัญหาพารามิเตอร์ทั้งหมดที่มีฟังก์ชันที่คำนวณได้และอัลกอริทึมที่ตัดสินค่าL ได้ ในเวลา ${\displaystyle (L,k)}$${\displaystyle f:\mathbb {N} \to \mathbb {N} }$${\displaystyle f\in o(k)}$${\displaystyle 2^{f(k)}\cdot {\textsf {poly}}(n)}$

สมมติฐานเวลาเลขชี้กำลัง ( ETH ) คือ3SAT ซึ่ง เป็นปัญหาความพึงพอใจของสูตรบูลีนในรูปแบบปกติเชิงเชื่อมโยงที่มีตัวอักษรไม่เกินสามตัวต่อข้อความและมี ตัวแปร nตัว ไม่สามารถแก้ไขได้ในเวลา 2 ^{o ( n )}กล่าวโดยละเอียด สมมติฐานคือมีค่าคงที่สัมบูรณ์c > 0 บางค่า ที่ทำให้ 3SAT ไม่สามารถตัดสินได้ในเวลา 2 ^cnโดยเครื่องจักรทัวริงเชิงกำหนดใดๆ โดยที่mแทนจำนวนข้อความ ETH เทียบเท่ากับสมมติฐานที่ว่าk SAT ไม่สามารถแก้ไขได้ในเวลา 2 ^{o ( m )}สำหรับจำนวนเต็มk ≥ 3ใด ๆ ^{[ 26 ]}สมมติฐานเวลาเลขชี้กำลังบ่งชี้ว่าP ≠ NP

กล่าวได้ว่าอัลกอริทึมมีเวลาแบบเอก^{ซ์โปเนนเชียลถ้า} T ( n )มีค่าสูงสุดไม่เกิน 2ⁿⁿ โดยที่ poly( n ) คือพหุนามบางตัวในnกล่าวอย่างเป็นทางการมากขึ้น อัลกอริทึมมีเวลาแบบเอกซ์โปเนนเชียล ถ้าT(n) มีค่าสูงสุดไม่เกิน O(2ⁿᵏ) สำหรับค่าคงที่ k บางค่าปัญหาที่ยอมรับอั^ลกอริ^ทึม เวลาแบบเอกซ์โปเนนเชียลบ น เครื่องทัวริงแบบกำหนดได้ จะจัดอยู่ในกลุ่มความซับซ้อนที่เรียกว่าEXP

${\displaystyle {\textsf {EXP}}=\bigcup _{c\in \mathbb {R_{+}} }{\textsf {DTIME}}\left(2^{n^{c}}\right)}$

บางครั้ง เวลาแบบเลขชี้กำลังถูกใช้เพื่ออ้างถึงอัลกอริทึมที่มีT ( n ) = ^{2O ( n )}โดยที่เลขชี้กำลังเป็นฟังก์ชันเชิงเส้นของn อย่างมาก ซึ่งทำให้เกิดคลาสความซับซ้อนE

${\displaystyle {\textsf {E}}=\bigcup _{c\in \mathbb {N} }{\textsf {DTIME}}\left(2^{cn}\right)}$

กล่าวได้ว่าอัลกอริทึมมีเวลาแฟกทอเรียลถ้าT(n)มีค่าสูงสุดไม่เกินฟังก์ชันแฟกทอเรียลn!เวลาแฟกทอเรียลเป็นเซตย่อยของเวลาเอกซ์โพเนนเชียล (EXP) เพราะสำหรับทุกn ∈ n! อย่างไรก็ตาม มันไม่ใช่เซตย่อยของ E ${\displaystyle n!\leq n^{n}=2^{n\log n}=O\left(2^{n^{1+\epsilon }}\right)}$${\displaystyle \epsilon >0}$

ตัวอย่างหนึ่งของอัลกอริทึมที่ทำงานในเวลาแฟกทอเรียลคือโบโกซอร์ต (Bogosort)ซึ่งเป็นอัลกอริทึมการเรียงลำดับที่ไม่มีประสิทธิภาพอย่างมากโดยอาศัยการลองผิดลองถูก โบโกซอร์ตเรียงลำดับรายการที่มีnรายการโดยการสับเปลี่ยนรายการซ้ำ ๆ จนกว่าจะพบว่าเรียงลำดับแล้ว ในกรณีเฉลี่ย แต่ละรอบของการทำงานของอัลกอริทึมโบโกซอร์ตจะตรวจสอบลำดับหนึ่งในn ! ลำดับของ รายการ nรายการ หากรายการแตกต่างกัน จะมีเพียงลำดับเดียวเท่านั้นที่ถูกเรียงลำดับ โบโกซอร์ตมีที่มาเดียวกันกับทฤษฎีลิงอนันต์ (Infinite Monkey Theorem )

กล่าวกันว่าอัลกอริทึมมี เวลา การทำงานแบบเลขชี้กำลังสองเท่า (double exponential time) ถ้าT ( n ) มีค่าสูงสุดไม่เกิน^{2²poly ( n )}โดยที่ poly( n ) เป็นพหุนามบางตัวในnอัลกอริทึมดังกล่าวจัดอยู่ในกลุ่มความซับซ้อน2- EXPTIME

${\displaystyle {\textsf {2-EXPTIME}}=\bigcup _{c\in \mathbb {N} }{\textsf {DTIME}}\left(2^{2^{n^{c}}}\right)}$

อัลกอริทึมที่มีเวลาการทำงานแบบเลขชี้กำลังสองเท่าที่เป็นที่รู้จักกันดี ได้แก่:

• ขั้นตอนการตัดสินใจสำหรับเลขคณิตของเพรสเบอร์เกอร์
• การคำนวณฐาน Gröbner (ในกรณีที่เลวร้ายที่สุด^{[ 27 ]} )
• การกำจัดตัวบ่งปริมาณในฟิลด์ปิดจริงใช้เวลาอย่างน้อยสองเท่าของเวลาเลขชี้กำลัง^{[ 28 ]}และสามารถทำได้ในเวลานี้^{[ 29 ]}

• สัญกรณ์แอล
• ความซับซ้อนของพื้นที่