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

ให้uเป็นลำดับของสัญลักษณ์จากตัวอักษร (อาจเป็นอนันต์) กำหนดฟังก์ชัน p _u ( n ) ของจำนวนเต็มบวกnให้เป็นจำนวนตัวประกอบที่แตกต่างกัน (สตริงย่อยที่ต่อเนื่องกัน) ที่มีความยาวⁿจากสตริง  u [ ^{1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ]}

สำหรับสตริงuที่มีความยาวอย่างน้อยnบนตัวอักษรที่มีขนาดkเราจะเห็นได้อย่างชัดเจนว่า

${\displaystyle 1\leq p_{u}(n)\leq k^{n}\ ,}$

ขอบเขตที่บรรลุได้ด้วยคำคงที่และคำแยกส่วน [ ^{6 ] ตัวอย่าง}เช่นคำ Champernowneตามลำดับ^{[ 7 ]} สำหรับคำอนันต์uเรามีp _u ( n ) ที่มีขอบเขตหากuเป็นคาบในที่สุด (ลำดับจำกัด อาจว่างเปล่า ตามด้วยวัฏจักรจำกัด) ในทางกลับกัน ถ้าp _u ( n ) ≤ nสำหรับn บางค่า uจะเป็นคาบในที่สุด^{[ 3 ] [ 8 ]}

ลำดับที่ไม่เป็นคาบคือลำดับที่ไม่เป็นคาบในที่สุด ลำดับที่ไม่เป็นคาบมีฟังก์ชันความซับซ้อนที่เพิ่มขึ้นอย่างเคร่งครัด (นี่คือทฤษฎีบทของมอร์ส-เฮดลันด์ ) ^{[ 9 ] [ 10 ]}ดังนั้นp ( n ) อย่างน้อยก็n +1 ^{[ 11 ]}

เซตSของคำไบนารีจำกัดจะสมดุลก็ต่อเมื่อสำหรับแต่ละnเซตย่อยS _nของคำที่มีความยาวnมีคุณสมบัติที่ว่าน้ำหนักแฮมมิงของคำในS _nมีค่าที่แตกต่างกันไม่เกินสองค่าลำดับที่สมดุลคือลำดับที่เซตของตัวประกอบสมดุล^{[ 12 ]} ลำดับที่สมดุลมีฟังก์ชันความซับซ้อนไม่เกินn +1 ^{[ 13 ]}

คำSturmianบนตัวอักษรไบนารีคือคำที่มีฟังก์ชันความซับซ้อนn  + 1 ^{[ 14 ]} ลำดับจะเป็น Sturmian ก็ต่อเมื่อเป็นลำดับสมดุลและไม่เป็นคาบ^{[ 2 ] [ 15 ]} ตัวอย่างคือคำFibonacci ^{[ 14 ] [ 16 ]} โดยทั่วไป คำ Sturmian บนตัวอักษรขนาดkคือคำที่มีความซับซ้อนn + k −1 คำ Arnoux-Rauzy บนตัวอักษรไตรนารีมีความซับซ้อน 2 ⁿ +  1: ^{[ 14 ]}ตัวอย่างคือคำ Tribonacci ^{[ 17} ]

สำหรับคำที่เกิดซ้ำซึ่งแต่ละปัจจัยปรากฏเป็นอนันต์ครั้ง ฟังก์ชันความซับซ้อนเกือบจะกำหนดลักษณะของเซตของปัจจัย: ถ้าsเป็นคำที่เกิดซ้ำที่มีฟังก์ชันความซับซ้อนเหมือนกับtแล้วsจะมีเซตของปัจจัยเหมือนกับtหรือ δ t โดยที่ δ หมาย ^ถึงมอร์ฟิซึมการซ้ำตัวอักษรa → aa ^{[ 18} ]

ให้Lเป็นภาษาเหนือตัวอักษร และกำหนดฟังก์ชันp _L ( n ) ของจำนวนเต็มบวกnให้เป็นจำนวนคำที่แตกต่างกันที่มีความยาวnในL ^{[ 9 ]} ดังนั้นฟังก์ชันความซับซ้อนของคำจึงเป็นฟังก์ชันความซับซ้อนของภาษาที่ประกอบด้วยปัจจัยของคำนั้น

ฟังก์ชันความซับซ้อนของภาษามีข้อจำกัดน้อยกว่าฟังก์ชันความซับซ้อนของคำ ตัวอย่างเช่น อาจมีขอบเขตแต่ไม่คงที่ในที่สุด: ฟังก์ชันความซับซ้อนของภาษาปกติ มีค่า 3 และ 4 สำหรับ n คี่และคู่n ≥ 2 ตามลำดับ มีสิ่งที่คล้ายกับทฤษฎีบท Morse–Hedlund: ถ้าความซับซ้อนของLเป็นไปตามp _L ( n ) ≤ nสำหรับn บางค่า แล้วp _LจะมีขอบเขตและมีภาษาจำกัดFเช่นนั้น^{[ 9 ]}${\displaystyle a(bb)^{*}a}$

${\displaystyle L\subseteq \{xy^{k}z:x,y,z\in F,\ k\in \mathbb {N} \}\ .}$

ภาษาพหุนามหรือภาษาเบาบางคือภาษาที่ฟังก์ชันความซับซ้อนp ( n ) ถูกจำกัดด้วยกำลังคงที่ของnภาษาปกติที่ไม่ใช่พหุนามคือ^ภาษาเลขชี้กำลัง : มีn มากมายนับไม่ถ้วน ที่p ( n ) มากกว่าkn สำหรับ k > 1 ที่กำหนดไว้^{[ 19 ]}

เอนโทรปีเชิงทอพอโลยีของลำดับอนันต์uถูกกำหนดโดย

${\displaystyle H_{\mathrm {top} }(u)=\lim _{n\rightarrow \infty }{\frac {\log p_{u}(n)}{n\log k}}\ .}$

ขีดจำกัดมีอยู่เนื่องจากลอการิทึมของฟังก์ชันความซับซ้อนเป็นแบบย่อยบวก [ ^{20 ] [ 21 ] จำนวน}จริง ทุก จำนวน ระหว่าง 0 และ 1 เกิดขึ้นเนื่องจากเอนโทรปีเชิงโทโพโลยีของลำดับบางลำดับนั้นสามารถนำไปใช้ได้^{[ 22 ]}ซึ่งอาจถือได้ว่าเป็นแบบเวียนเกิดสม่ำเสมอ^{[ 23 ]}หรือแม้กระทั่งเป็นแบบเออร์โกดิกที่ไม่ซ้ำกัน^{[ 24 ]}

สำหรับxที่เป็นจำนวนจริงและbที่เป็นจำนวนเต็ม ≥ 2 ฟังก์ชันความซับซ้อนของxในฐานbคือฟังก์ชันความซับซ้อนp ( x , b , n ) ของลำดับตัวเลขของxที่เขียนในฐานbถ้าxเป็นจำนวนอตรรกยะp ( x , b , n ) ≥ n +1 ถ้าx เป็นจำนวนตรรกยะp ( x , b , n ) ≤ Cสำหรับ ค่าคงที่ Cบางค่าที่ขึ้นอยู่กับxและb ^{[ 6 ]} มีการคาดการณ์ว่าสำหรับจำนวนอตรรกยะเชิงพีชคณิตxความซับซ้อนคือb ⁿ (ซึ่งจะเป็นไปตามนั้นหากจำนวนดังกล่าวทั้งหมดเป็นจำนวน^ปกติ )แต่สิ่งที่ทราบในกรณีนี้คือpเติบโตเร็วกว่าฟังก์ชันเชิงเส้นใดๆ ของn ^{[ 25} ]

ฟังก์ชันความซับซ้อนแบบอาเบลียนp ^ab ( n ) นับจำนวนการเกิดของปัจจัยที่แตกต่างกันที่มีความยาวn ที่กำหนด โดยที่ตอนนี้เราระบุปัจจัยที่แตกต่างกันเฉพาะการเรียงสับเปลี่ยนตำแหน่งเท่านั้น เห็นได้ชัดว่าp ^ab ( n ) ≤ p ( n ) ความซับซ้อนแบบอาเบลียนของลำดับ Sturmian เป็นไปตามp ^ab ( n ) = 2 ^{[ 26 ]}