Array – Example – 基本題
\(
\newcommand{\ord}[1]{\mathcal{O}\left(#1\right)}
\newcommand{\abs}[1]{\lvert #1 \rvert}
\newcommand{\floor}[1]{\lfloor #1 \rfloor}
\newcommand{\ceil}[1]{\lceil #1 \rceil}
\newcommand{\opord}{\operatorname{\mathcal{O}}}
\newcommand{\fail}{\operatorname{\mathcal{F}}}
\newcommand{\flk}{\operatorname{\mathfrak{F}}}
\newcommand{\suf}{\operatorname{\sigma}}
\newcommand{\rank}{\operatorname{\mathcal{R}}}
\newcommand{\sa}{\operatorname{\mathcal{SA}}}
\newcommand{\hei}{\operatorname{\mathcal{H}}}
\newcommand{\edps}{\operatorname{\mathcal{E}}}
\newcommand{\mx}{\operatorname{\mathcal{M}}}
\newcommand{\argmax}{\operatorname{arg\,max}}
\newcommand{\cons}[1]{\left[ \: #1 \: \right]}
\newcommand{\str}[1]{\texttt{"#1"}}
\)
阿n=10^4勒?
Array
alechuang98
有一天你突然要存三個整數
int main(){
int val_1,val_2,val_3;
}
如果要存10^6個整數呢?
int main(){
int val_1,val_2,...,val_1000000;
}
等code完應該都已經天黑了吧...
這時候就需要神奇的陣列
- 宣告: int a[1000000];
- 這裡a[i]的i稱為index值，可以是整數變數
- 這時候就有了從a[0]~a[99999]的元素
- 存取第i個元素:a[i-1]
- 那當然也可以int a[1000001];，取 1~1000000 來用
int a[1000000];
int main(){
int i,n,x;
scanf("%d",&n);
for(i = 0 ; i < n ; i ++ )
scanf("%d",&a[i]);
printf("%d",a[x]);
}
Example
基本題
- 第一行輸入整數n
- 第二行輸入整數l,r(編號由1~n)
- 第三行輸入n個數ai
- 請輸出[l,r]的平均值無條件捨去至整數
- 保證1<=l<=r<=n<=1000000-1000<=ai<=1000
排序
輸入n個整數把這n個數由小到大排序怎麼做呢?
看一下n比較小的情況吧
假設現在 n=3 好了
反正 n=3 時也才 3!=6 種case而已，就if一一討論吧
不只要把一棵樹序列化，還希望一個子樹就對應到一個區間。if 討論 ?10000! = 2.84625968091705451890641321211986889014805140170279... × 10^35659很瘟腥對吧
想像一下現在你有10顆球，１編號1~10，請你幫我把它們由小到大排
你會...
- 先從這10顆中挑最小的放到最左邊編號1的位置
- 再從剩下的9顆中挑最小的放到2號位置
- 再從剩下的8顆中挑最小的放到3號位置...
SELECTION SORT 選擇排序法
具體作法就是從每次現有的k個元素中取最小(大)值，放到最左邊後繼續做剩下的k-1個元素
Selection Sort
int a[10000];
int main(){
int i,j,n,tmp;
for(i = 0 ; i < n-1 ; i ++ ){
for(j = i+1 ; j< n ; j++){
if(a[i]>a[j]){
tmp=a[i]; //變數變換很重要喔
a[i]=a[j];
a[j]=tmp;
}
}
}
}
來看一點進階觀念
假設電腦在做加減乘除與賦值運算所花的時間是一樣的一個演算法可以定義他所需的計算次數我們又稱他做"時間複雜度"
而在資訊競賽中我們口中常說的複雜度是一個演算法在 "最差情況下" 所需的計算次數假設某個演算法在最差情況下須進行k次運算我們就將它的複雜度表示為 O(k)
回到selection sort 我們仔細算一下發現他最差約需要交換 n(n-1)/2 次
而我們假設n超大此時 n(n-1)/2 近似於 n^2我們說選擇排序法的複雜度是O(n^2)
複雜度分析是資訊競賽中相當重要的一環其中又分為空間和時間複雜度而一個演算法的快慢就是由時間複雜度影響以剛剛的排序法來說，除了O(n^2)外還有其他算法有O(nlogn)的複雜度當n到10^6次方時n^2和nlogn的運算時間在一般電腦上運行可以相差10000多秒
更多有關時間複雜度內容的可以自行去查資料
Arrayalechuang98