平行計算是指同時使用多個計算機處理器 (CPU) 而不是僅使用一個處理器來執行計算機程式。令 
為最快的已知序列演算法的執行時間，令 
為在 
個處理器上執行的並行演算法的執行時間，其中 
是輸入的大小。
加速比定義為
 |
即，序列執行時間與並行執行時間的比率。理想情況下，人們希望 
，這被稱為完美加速比，儘管在實踐中很少實現。（在某些情況下，由於記憶體層次結構效應，可以實現超線性加速比。）
衡量並行演算法效能的另一個指標是效率，
，定義為
 |
人們可以使用加速比和效率來分析演算法，可以從理論上使用漸近執行時複雜度，也可以在實踐中透過測量程式執行時間。當 
固定時，加速比和效率是等效的度量，僅相差常數因子 
。
