01 时间复杂度与空间复杂度#

我们衡量算法的优劣主要通过两个维度时间``空间,而这两个维度对应的就是时间复杂度``空间复杂度. 但鱼和熊掌不可兼得,我们只能在这两者间取得一个合适的平衡点

1.时间复杂度#

算法所需要的时间工作量

标记公式
- T(n) = O(n)

常见的时间复杂度量级#

a.常数阶O(1)#

1
int i = 1;
2
int j = 2;
3
++i;
4
j++;
5
int m = i + j;

b.线性阶O(n)#

1
for(i=1; i<=n; ++i)
2
{
3
   j = i;
4
   j++;
5
}

c.对数阶O(logN)#

以2为底

1
int i = 1;
2
while(i<n)
3
{
4
    i = i * 2;
5
}

d.线性对数阶(nlogN)#

1
for(m=1; m<n; m++)
2
{
3
    i = 1;
4
    while(i<n)
5
    {
6
        i = i * 2;
7
    }
8
}

e.平方阶(n²)#

1
for(x=1; i<=n; x++)
2
{
3
   for(i=1; i<=n; i++)
4
    {
5
       j = i;
6
       j++;
7
    }
8
}

如果把一层循环的n改成m,时间复杂度就成了 O(m*n)

1
for(x=1; i<=m; x++)
2
{
3
   for(i=1; i<=n; i++)
4
    {
5
       j = i;
6
       j++;
7
    }
8
}

f.立方阶O(n³)、K次方阶O(n^k)#

参考的O(n²),O(n³)相当于三层n循环

2.空间复杂度#

算法在运算中临时占用的控件的大小

标记公式
- S(n) = O(n)

常见的空间复杂度量级#

a. O(1)#

如果算法执行所需要的临时空间不随着某个变量n的大小而变化，即此算法空间复杂度为一个常量，可表示为 O(1)

1
int i = 1;
2
int j = 2;
3
++i;
4
j++;
5
int m = i + j;

b. O(n)#

1
int[] m = new int[n]
2
for(i=1; i<=n; ++i)
3
{
4
   j = i;
5
   j++;
6
}

这段代码中，第一行new了一个数组出来，这个数据占用的大小为n，这段代码的2-6行，虽然有循环，但没有再分配新的空间，因此，这段代码的空间复杂度主要看第一行即可，即 S(n) = O(n)

02 排序题#

这里简单的说下几种快速排序的不同之处，随机快排，是为了解决在近似有序的情况下，时间复杂度会退化为O(n^2),双路快排是为了解决快速排序在大量数据重复的情况下，时间复杂度会退化为O(n^2)，三路快排是在大量数据重复的情况下，对双路快排的一种优化。

冒泡排序#

1
extension Array where Element : Comparable{
2
    public mutating func bubbleSort() {
3
        let count = self.count
4
        for i in 0..<count {
5
            for j in 0..<(count - 1 - i) {
6
                if self[j] > self[j + 1] {
7
                    (self[j], self[j + 1]) = (self[j + 1], self[j])
8
                }
9
            }
10
        }
11
    }
12
}

选择排序#

1
extension Array where Element : Comparable{
2
    public mutating func selectionSort() {
3
        let count = self.count
4
        for i in 0..<count {
5
            var minIndex = i
6
            for j in (i+1)..<count {
7
                if self[j] < self[minIndex] {
8
                    minIndex = j
9
                }
10
            }
11
            (self[i], self[minIndex]) = (self[minIndex], self[i])
12
        }
13
    }
14
}

插入排序#

1
extension Array where Element : Comparable{
2
    public mutating func insertionSort() {
3
        let count = self.count
4
        guard count > 1 else { return }
5
        for i in 1..<count {
6
            var preIndex = i - 1
7
            let currentValue = self[i]
8
            while preIndex >= 0 && currentValue < self[preIndex] {
9
                self[preIndex + 1] = self[preIndex]
10
                preIndex -= 1
11
            }
12
            self[preIndex + 1] = currentValue
13
        }
14
    }
15
}

快速排序#

1
extension Array where Element : Comparable{
2
    public mutating func quickSort() {
3
        func quickSort(left:Int, right:Int) {
4
            guard left < right else { return }
5
            var i = left + 1,j = left
6
            let key = self[left]
7
            while i <= right {
8
                if self[i] < key {
9
                    j += 1
10
                    (self[i], self[j]) = (self[j], self[i])
11
                }
12
                i += 1
13
            }
14
            (self[left], self[j]) = (self[j], self[left])
15
            quickSort(left: j + 1, right: right)
16
            quickSort(left: left, right: j - 1)
17
        }
18
        quickSort(left: 0, right: self.count - 1)
19
    }
20
}

随机快排#

1
extension Array where Element : Comparable{
2
    public mutating func quickSort1() {
3
        func quickSort(left:Int, right:Int) {
4
            guard left < right else { return }
5
            let randomIndex = Int.random(in: left...right)
6
            (self[left], self[randomIndex]) = (self[randomIndex], self[left])
7
            var i = left + 1,j = left
8
            let key = self[left]
9
            while i <= right {
10
                if self[i] < key {
11
                    j += 1
12
                    (self[i], self[j]) = (self[j], self[i])
13
                }
14
                i += 1
15
            }
16
            (self[left], self[j]) = (self[j], self[left])
17
            quickSort(left: j + 1, right: right)
18
            quickSort(left: left, right: j - 1)
19
        }
20
        quickSort(left: 0, right: self.count - 1)
21
    }
22
}

双路快排#

1
extension Array where Element : Comparable{
2
    public mutating func quickSort2() {
3
        func quickSort(left:Int, right:Int) {
4
            guard left < right else { return }
5
            let randomIndex = Int.random(in: left...right)
6
            (self[left], self[randomIndex]) = (self[randomIndex], self[left])
7
            var l = left + 1, r = right
8
            let key = self[left]
9
            while true {
10
                while l <= r && self[l] < key {
11
                    l += 1
12
                }
13
                while l < r && key < self[r]{
14
                    r -= 1
15
                }
16
                if l > r { break }
17
                (self[l], self[r]) = (self[r], self[l])
18
                l += 1
19
                r -= 1
20
            }
21
            (self[r], self[left]) = (self[left], self[r])
22
            quickSort(left: r + 1, right: right)
23
            quickSort(left: left, right: r - 1)
24
        }
25
        quickSort(left: 0, right: self.count - 1)
26
    }
27
}

三路快排#

1
// 三路快排
2
extension Array where Element : Comparable{
3
    public mutating func quickSort3() {
4
        func quickSort(left:Int, right:Int) {
5
            guard left < right else { return }
6
            let randomIndex = Int.random(in: left...right)
7
            (self[left], self[randomIndex]) = (self[randomIndex], self[left])
8
            var lt = left, gt = right
9
            var i = left + 1
10
            let key = self[left]
11
            while i <= gt {
12
                if self[i] == key {
13
                    i += 1
14
                }else if self[i] < key{
15
                    (self[i], self[lt + 1]) = (self[lt + 1], self[i])
16
                    lt += 1
17
                    i += 1
18
                }else {
19
                    (self[i], self[gt]) = (self[gt], self[i])
20
                    gt -= 1
21
                }
22

23
            }
24
            (self[left], self[lt]) = (self[lt], self[left])
25
            quickSort(left: gt + 1, right: right)
26
            quickSort(left: left, right: lt - 1)
27
        }
28
        quickSort(left: 0, right: self.count - 1)
29
    }
30
}