经常听到”牺牲时间换空间“,”牺牲空间换时间“。

可见,算法好坏衡量规则就在于时间、空间上面。

算法好坏统计方法

事后统计法。依赖于测试数据,如果你要一顿数字查找2在第几个位置,如果第一个数字就是2,效率就极高

事前估算分析法:分析出最坏的情况,统计执行次数

二分查找:n是元素格式,执行次数:floor(log_2(n) + 1)

时间复杂度

一个算法随着数据规模的增大而增大的时间成本。一般用大O表示法。

O(1):时间成本与数据规模没关系。

O(N):N越大,时间成本越高

空间复杂度

一个算法随着数据规模增大而额外增加的空间成本。也是用大O表示法