多對數函式

n的多對數函式（polylogarithmic function）是指n的對數的多項式。

基本介紹

• 中文名：多對數函式
• 外文名：polylogarithmic function
• 定義：n的對數的多項式
• 學科：計算機科學
• 領域：計算機科學
• 理論：計算複雜性理論

簡介

n的多對數函式（polylogarithmic function）是指n的對數的多項式

在計算機科學中，多對數函式在一些算法空間複雜度的數量級中用到（多對數級）。

所有多對數函式都符合以下的形式

對於每個大於0的指數，也就是說，多對數函式成長的比每任何正指數的多項式函式都要慢。

參見

計算複雜性理論

計算複雜性理論所研究的資源中最常見的是時間（要通過多少步演算才能解決問題）和空間（在解決問題時需要多少存儲器）。其他資源亦可考慮，例如在並行計算中，需要多少並行處理器才能解決問題。

時間複雜度是指在計算機科學與工程領域完成一個算法所需要的時間，是衡量一個算法優劣的重要參數。時間複雜度越小，說明該算法效率越高，則該算法越有價值。

空間複雜度是指計算機科學領域完成一個算法所需要占用的存儲空間，一般是輸入參數的函式。它是算法優劣的重要度量指針，一般來說，空間複雜度越小，算法越好。我們假設有一個圖靈機來解決某一類語言的某一問題，設有{\displaystyle X}個字（word）屬於這個問題，把{\displaystyle X}放入這個圖靈機的輸入端，這個圖靈機為解決此問題所需要的工作帶格子數總和稱為空間。

複雜度理論和可計算性理論不同，可計算性理論的重心在於問題能否解決，不管需要多少資源。而複雜性理論作為計算理論的分支，某種程度上被認為和算法理論是一種“矛”與“盾”的關係，即算法理論專注於設計有效的算法，而複雜性理論專注於理解為什麼對於某類問題，不存在有效的算法。

多項式

多項式（Polynomial）是代數學中的基礎概念，是由稱為未知數的變數和稱為係數的常數通過有限次加減法、乘法以及自然數冪次的乘方運算得到的代數表達式。多項式是整式的一種。未知數只有一個的多項式稱為一元多項式；例如 x²-3x+4就是一個一元多項式。未知數不止一個的多項式稱為多元多項式，例如x³+2xyz²-yz+1就是一個三元多項式。

可以寫成只由一項構成的多項式也稱為單項式。如果一項中不含未知數，則稱之為常數項。

多項式在數學的很多分支中乃至許多自然科學以及工程學中都有重要作用。