1 回答

TA貢獻1833條經驗 獲得超4個贊
簡單理解,時間復雜度就是執行語句被調用了多少次。
(1)如果只調用了一次,如:
x=5;
if(x<-4)
{x=x+4;}
else
{x=x+3;}
在大括號中的內容,只會調用一個語句,那么O(n)=1;
(2)如果調用了兩次,如:
x=5;
if(x<-4)
{x=x+4;}
else
{x=x+3;}
x=x+56;
在大括號中的內容,只會調用一個語句,但是在最后,還有一個計算公式要調用語句;總共加起來就是調用2次。那么O(n)=2;
(3)用1個FOR循環調用
for(x=0;x<n;x++)
{x=x+1;}
x會從0到n-1循環,執行的語句就是將當前x值加入新的x中,總共調用n次;那么O(n)=n;
(4)用2個嵌套FOR循環調用
for(x=0;x<n;x++)
{
for(y=1;y<=n;y++)
{x=x+y;}
}
遇到嵌套循環,可以先將外面的FOR語句中的變量固定為初始值x=0,主要看里面的FOR語句的時間復雜度,很明顯,里面語句執行次數是從1到n總共調用n次,O(n)=n;這還只是x=0時的調用。x可以從0到n-1,共n次。每次調用都會執行n次調用y的情況,因此,執行語句x=x+y;總共會調用n*n次。O(n)=n^2。
數執行語句的執行次數,就是時間復雜度。注意:
(1)找到正確的執行語句。
(2)for循環中的初始值和終止值。
for(i=0;i<n;i++) i值變化是從0到n-1,共n次。
for(i=0;i<=n;i++) i值變化是從0到n,共n+1次。
(3)注意for循環的調用順序,從里面到外面進行的。
- 1 回答
- 0 關注
- 680 瀏覽
添加回答
舉報