ในทฤษฎีความซับซ้อนฟังก์ชันที่สร้างได้ในเวลาคือฟังก์ชันfจากจำนวนธรรมชาติไปยังจำนวนธรรมชาติที่มีคุณสมบัติว่าf ( n ) สามารถสร้างจากn ได้ โดยเครื่องจักรทัวริงในเวลาลำดับf ( n ) จุดประสงค์ของคำจำกัดความดังกล่าวคือการยกเว้นฟังก์ชันที่ไม่ให้ขอบเขตบนของรันไทม์ของเครื่องจักรทัวริงบางเครื่อง^{[ 1 ]}

ให้เครื่องจักรทัวริงถูกกำหนดในรูปแบบมาตรฐาน โดยใช้ตัวอักษรที่ประกอบด้วยสัญลักษณ์ และมีเทปอินพุตมาตรฐานที่ประกอบด้วยศูนย์ทั้งหมด ยกเว้นสตริงอินพุต ให้แทนสตริงที่ประกอบด้วยเลขหนึ่งทั้งหมด นั่นคือ เป็นการแสดงแทนแบบเอกภาคของและ ให้เป็นการแสดงแทนแบบทวิภาค${\displaystyle 0,1}$${\displaystyle 1^{n}}$${\displaystyle n}$${\displaystyle n}$${\displaystyle ||n|}$

ฟังก์ชันจะเรียกว่าสามารถสร้างได้ตามเวลา (time-constructible)หากมีเครื่องจักรทัวริงอยู่เครื่องหนึ่งที่การคำนวณจะหยุดลงในขั้นตอนที่มีค่าเท่ากับ ${\displaystyle f}$${\displaystyle M}$${\displaystyle M(1^{n})}$${\displaystyle O(f(n))}$${\displaystyle |f(n)|}$

คำจำกัดความนี้อาจใช้แทนได้ เนื่องจากทั้งสองสามารถแปลงระหว่างกันได้เป็นขั้นตอน^{[ 1 ]}${\displaystyle M(1^{n})=1^{f(n)}}$${\displaystyle O(f(n))}$

นอกจากนี้ยังมีแนวคิดเกี่ยวกับ ฟังก์ชันที่สามารถสร้างขึ้นได้ อย่างสมบูรณ์ตามเวลา อีก ด้วย

ฟังก์ชันเรียกว่าสามารถสร้างได้อย่างสมบูรณ์ตามเวลา หากมีเครื่องจักรทัวริงอยู่ซึ่งสำหรับค่า ยกเว้นค่าจำกัดจำนวนหนึ่งจะหยุดทำงานในเวลาเพียงขั้นตอน^{[ 2 ]}คำจำกัดความนี้มีความทั่วไปน้อยกว่าคำจำกัดความแรกเล็กน้อย แต่สำหรับการใช้งานส่วนใหญ่ สามารถใช้คำจำกัดความใดก็ได้^{[ 3 ]}ทฤษฎีบทสมมูลต่อไปนี้แสดงให้เห็นว่าแนวคิดทั้งสองนี้เทียบเท่ากันสำหรับฟังก์ชันส่วนใหญ่ที่ใช้ในทางปฏิบัติ: ${\displaystyle f}$${\displaystyle M}$${\displaystyle n}$${\displaystyle M(1^{n})}$${\displaystyle f(n)}$

ทฤษฎีบท^{[ 3 ] : ทฤษฎีบท 2.6} ถ้าเป็นฟังก์ชันที่มีอยู่จริง โดยที่ สำหรับทุก ยกเว้นจำนวนจำกัด( นั่นคือ ถ้า) แล้วสามารถสร้างได้ในเวลา ก็ต่อเมื่อสามารถสร้างได้ในเวลาอย่างสมบูรณ์ ${\displaystyle f}$${\displaystyle \epsilon >0}$${\displaystyle n}$${\displaystyle f(n)\geq (1+\เอปไซลอน )n}$${\displaystyle f(n)-n=\โอเมก้า (n)}$${\displaystyle f}$

ฟังก์ชันเรียกว่าสามารถสร้างได้ด้วยพื้นที่หากมีเครื่องจักรทัวริงอยู่ซึ่งหยุดทำงานด้วยค่า(หรือเทียบเท่า) ในขณะที่ใช้พื้นที่^{[ 1 ]}${\displaystyle f}$${\displaystyle M}$${\displaystyle M(1^{n})}$${\displaystyle |f(n)|}$${\displaystyle 1^{f(n)}}$${\displaystyle O(f(n))}$

ในทำนองเดียวกันเรียกว่าสามารถสร้างพื้นที่ได้ หากมีเครื่องจักรทัวริงอยู่ซึ่งสำหรับค่าทั้งหมด ยกเว้นค่าจำกัดจำนวนหนึ่งการคำนวณจะหยุดลงในการกำหนดค่าซึ่ง มีเซลล์ที่ไม่ว่างเปล่าอยู่ จำนวนหนึ่งพอดีและไม่มีเซลล์อื่นใดถูกเขียนลงไปในระหว่างการทำงาน^{[ 3 ] : นิยาม 2.4} บางครั้งเรียกว่า "สามารถสร้างพื้นที่ได้อย่างสมบูรณ์" อย่างไรก็ตาม นิยามทั้งสองนั้นเทียบเท่ากัน^{[ 3 ] : ทฤษฎีบท 2.7} ${\displaystyle f}$${\displaystyle M}$${\displaystyle n}$${\displaystyle M(1^{n})}$${\displaystyle f(n)}$

ฟังก์ชันที่ใช้กันทั่วไปทั้งหมด (เช่น) สามารถสร้างได้ทั้งในแง่ของเวลาและพื้นที่ ตราบใดที่การสร้างนั้นตรงไปตรงมา ตัวอย่างเช่นสร้างขึ้นโดยใช้ลูป for ซ้อนกันหนึ่งชั้น ในขณะที่สร้างขึ้นโดยใช้ลูป for ซ้อนกันสองชั้น เป็นต้น ${\displaystyle n,n^{2},2^{n},n!}$${\displaystyle f(n)=\โอเมก้า (n)}$${\displaystyle n^{2}}$${\displaystyle n^{3}}$

หากโครงสร้างนั้นสามารถสร้างขึ้นได้ภายในเวลาที่กำหนด ในที่สุดมันก็จะคงที่ เนื่องจากมิเช่นนั้นจะมีเวลาไม่เพียงพอที่จะอ่านข้อมูลอินพุตทั้งหมด ${\displaystyle f(n)=o(n)}$

${\displaystyle \ln n}$สามารถสร้างในอวกาศได้แม้ว่าจะเป็นเช่นนั้นก็ตาม ${\displaystyle \ln n=o(n)}$

สำหรับฟังก์ชันที่คำนวณได้ ทุกฟังก์ชัน จะมีฟังก์ชันที่คำนวณได้ซึ่งสามารถสร้างได้ในเวลาและ[ ^{3 ] :บทพิสูจน์ 2.3} ${\displaystyle f}$${\displaystyle g}$${\displaystyle \forall n,g(n)>f(n)}$

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

ฟังก์ชันที่สร้างได้ในอวกาศถูกนำมาใช้ในลักษณะเดียวกัน ตัวอย่างเช่น ในทฤษฎีบท ลำดับชั้นของอวกาศ