# 1092 Algorithm Ex2-C Report

###### tags: `courses` `Algorithm`

> 108502586; 鍾安;

:::info
檔案相關描述在 `README.md` 中
:::

## 實驗
實驗中時間以 clock 來表示
1,000,000 clock = 1 second

### Input
有兩個整數 $N$ 與 $M$，代表兩數列 $A$ 與 $B$ 的大小
$$
A = {a_1, a_2, a_3, ..., a_N} \\
B = {b_1, b_2, b_3, ..., b_M}
$$

N M
a_1
a_2
...
a_N
b_1
b_2
...
b_M

## Insert

### Method 1
程式會先 insert $N$ 個隨機數字，而後測試 insert 10,000 個數字所需的時間
$N$ 以 10,000 為級距，最大到 10,000,000

在 y 軸以指數成長的狀態下，一維 array 的 insert 成 log 圖樣，因此一維 array 的 insert time 應為線性。
dynamic binary search structure 則是幾乎沒有什麼改變，這是因為每次的測試為 insert 10,000 個數字，而每次所需要動到的 array 都是前面那幾個，後面還有多少數字並不會影響。

### Method 2
程式會先 insert 1 個隨機數字，而後測試 insert $M$ 個數字所需的時間
與 Method 1 的結果類似


y 軸以指數成長：

### 小測資
程式會先 insert 1 個隨機數字，而後測試 insert $M$ 個數字所需的時間：

在輸入的測試資料偏小時，一維 array 的 insert 有時會比較快。
dynamic binary search 的時間雖然波動很大，但是還是可以看出趨勢並不是線性的，而是小於線性。

## Search

### Method 1
程式會先 insert $N$ 個隨機數字，而後測試 search 10,000 個數字所需的時間

由於此份資料沒有做平均計算，機此時間波動很大，無法看出趨勢。
但是仍可看出 dynamic binary search structure 需要花費更多的時間

> 嘗試著取平均，但是時間實在是花太久了，而且波動仍然很大。
> 或許需要再多寫一個沒有使用 IO 的程式來測

## Deletion
先找到要刪除的元素所在的 array，稱為 $D$
找到 index 最小的 array(不為空)，稱為 $A$
將 $A_0$ insert 到 $D$ (使用 1 維 binary search array 的方式)
將 $A$ 中剩餘的元素分散到比他小的那些 array 空間中

### 例子：

若要刪除第 3 array 中的元素
則用第 2 array 的第一個元素去補齊第 3 array
然後再將第 2 array 剩餘元素依序填入第 1, 第 2 array
結果仍然符合規定

digraph {
  label="Step1\n"
  rankdir=LR
  node [shape=plaintext]
  dbsa [label=<
    <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="10">
      <TR PORT="a0">
        <TD> </TD>
      </TR>
      <TR PORT="a1">
        <TD> </TD>
        <TD> </TD>
      </TR>
      <TR PORT="a2">
        <TD PORT="target"><font color="blue">3</font></TD>
        <TD>4</TD>
        <TD>5</TD>
        <TD PORT="a2_end">6</TD>
      </TR>
      <TR PORT="a3">
        <TD PORT="a3_start">7</TD>
        <TD>8</TD>
        <TD>9</TD>
        <TD><font color="red">10</font></TD>
        <TD>11</TD>
        <TD>12</TD>
        <TD>13</TD>
        <TD PORT="a3_end">14</TD>
      </TR>
    </TABLE>
  >];
  
  A [label="A:\n the smallest array"]
  D [label="D:\n the array contained the\n element to be deleted"]
  
  dbsa:target:w -> dbsa:a3_start:w [label="insert"]
  dbsa:a2_end -> A [color=blue]
  dbsa:a3_end -> D [color=red]
}

digraph {
  label="Step 2"
  rankdir=LR
  node [shape=plaintext]
  dbsa [label=<
    <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="10">
      <TR PORT="a0">
        <TD PORT="a0_start"> </TD>
      </TR>
      <TR PORT="a1">
        <TD PORT="a1_start"> </TD>
        <TD> </TD>
      </TR>
      <TR PORT="a2">
        <TD PORT="target"><font color="red">3</font></TD>
        <TD>4</TD>
        <TD>5</TD>
        <TD>6</TD>
      </TR>
      <TR PORT="a3">
        <TD PORT="a3_start"><font color="blue">3</font></TD>
        <TD>7</TD>
        <TD>8</TD>
        <TD>9</TD>
        <TD>11</TD>
        <TD>12</TD>
        <TD>13</TD>
        <TD>14</TD>
      </TR>
    </TABLE>
  >];
  
  dbsa:target:w -> dbsa:a0_start:w [label="split  "]
  dbsa:target:w -> dbsa:a1_start:w
}

digraph {
  label="Step 3 / DONE"
  node [shape=plaintext]
  dbsa [label=<
    <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="10">
      <TR PORT="a0">
        <TD PORT="a0_start">4</TD>
      </TR>
      <TR PORT="a1">
        <TD PORT="a1_start">5</TD>
        <TD>6</TD>
      </TR>
      <TR PORT="a2">
        <TD PORT="target"> </TD>
        <TD> </TD>
        <TD> </TD>
        <TD> </TD>
      </TR>
      <TR PORT="a3">
        <TD>3</TD>
        <TD>7</TD>
        <TD>8</TD>
        <TD>9</TD>
        <TD>11</TD>
        <TD>12</TD>
        <TD>13</TD>
        <TD>14</TD>
      </TR>
    </TABLE>
  >];
}

### 分析
假設 index 最小的 array 長度為 $M_1$，要刪除的元素所在的 array 長度為 $M_2$，全部內容物大小為 $N$

補齊：$O(M_2)$
分散：$O(M_1)$
Total: $O(M_2 + M_1)$
將時間分散，平均: $O(\log n)$