快速冪(Exponentiation by squaring,平方求冪)是一種簡單而有效的小算法,它可以以的時間復(fù)雜度計算乘方。快速冪不僅本身非常常見,而且后續(xù)很多算法也都會...
快速冪(Exponentiation by squaring,平方求冪)是一種簡單而有效的小算法,它可以以的時間復(fù)雜度計算乘方。快速冪不僅本身非常常見,而且后續(xù)很多算法也都會...
所謂圖(graph),是圖論中基本的數(shù)學(xué)對象,包括一些頂點(diǎn),和連接頂點(diǎn)的邊,這里的邊只是表示頂點(diǎn)的連接情況,用直線或曲線表示均可。圖可以分為有向圖和無向圖,有向圖中的邊是有方...
素數(shù)篩法,是一種快速“篩”出2~n之間所有素數(shù)的方法。樸素的篩法叫埃氏篩(the Sieve ofEratosthenes,埃拉托色尼篩),它的過程是這樣的: 我們把2~n的...
中國剩余定理,也叫孫子定理,之所以叫這個名字,是因為《孫子算經(jīng)》中有這樣一個問題: 有物不知其數(shù),三三數(shù)之剩二,五五數(shù)之剩三,七七數(shù)之剩二。問物幾何? 這個被叫做“物不知數(shù)”...
樹狀數(shù)組(Binary Index Tree, BIT)也是很多OIer心中最簡潔優(yōu)美的數(shù)據(jù)結(jié)構(gòu)之一。最簡單的樹狀數(shù)組支持兩種操作,時間復(fù)雜度均為 : 單點(diǎn)修改:更改數(shù)組中...
并查集被很多OIer認(rèn)為是最簡潔而優(yōu)雅的數(shù)據(jù)結(jié)構(gòu)之一,主要用于解決一些元素分組的問題。它管理一系列不相交的集合,并支持兩種操作: 合并(Union):把兩個不相交的集合合并為...