稀疏陣列

Sparse Matrix是一個用來存取有需多空值陣列的解決方法。

解決的問題：

Sparse Matrix可以將一個包含許多0的2 dimension array 轉換為只要存取不為0的欄位，這樣可以省下許多的空間。

優點：

1. 要找到array中非0的資料比較快

2. 要找到array中特定value的資料比2 dimension array快

   2 dimension array需要找到所有非0資料的方法為 $O(n^2)$，Sparse Matrix為 $O(n)$

缺點：

1. Sparse Matrix會導致get&set的時候變慢

例如：

我希望要在array[10][10]裡面找到array[3][4]的值，我需要遍尋所有SparseMatrix中的Triple，去一一比對每一個Triple中所存取的row&col，最差的情況下是 $O(n)$

    get(row, col) {
        for (const triple of this.triples) {
            if (triple.row === row && triple.col === col) {
                return triple.value;
            }
        }
        return 0;
    }

    set(row, col, value) {
        if (value === 0) {
            return false;
        }
        if (this.rows <= row || this.cols <= col) {
            throw new Error("Index out of bounds");
        }
        for (const triple of this.triples) {
            if (triple.row === row && triple.col === col) {
                triple.value = value;
                return true;
            }
        }
        this.triples.push({ row, col, value });
        return true;
    }