時(shí)間復(fù)雜度是衡量算法性能的重要指標(biāo)，用來描述算法隨著輸入規(guī)模 n 增大，運(yùn)行時(shí)間的增長(zhǎng)趨勢(shì)。以下是時(shí)間復(fù)雜度的核心概念與常見分類的詳細(xì)講解。

1. 時(shí)間復(fù)雜度的定義

時(shí)間復(fù)雜度反映了算法執(zhí)行的 基本操作數(shù)量 與輸入規(guī)模 n 的關(guān)系。它通常使用大 O表示法來表示，即：

其中 f(n)是輸入規(guī)模 n 的函數(shù)，代表操作數(shù)量的增長(zhǎng)速度。

2. 常見時(shí)間復(fù)雜度

時(shí)間復(fù)雜度可以分為常數(shù)、對(duì)數(shù)、線性、多項(xiàng)式、指數(shù)等不同增長(zhǎng)級(jí)別。以下是常見時(shí)間復(fù)雜度，從快到慢排序：

2.1 O(1) - 常數(shù)時(shí)間復(fù)雜度

• 概念：無(wú)論輸入規(guī)模多大，算法的運(yùn)行時(shí)間都固定不變。
• 示例：訪問數(shù)組某個(gè)索引元素。

arr = [1, 2, 3, 4]
x = arr[2]  # O(1)

• 特性：效率極高，常見于簡(jiǎn)單的數(shù)學(xué)運(yùn)算或直接訪問。

2.2 O(log n) -