1.演算法效率
演算法效率分析分為兩種：第一種是時間效率，第二種是空間效率，時間效率被稱為時間復雜度，而空間效率被稱作空間復雜度， 時間復雜度主要衡量的是一個演算法的運行速度，而空間復雜度主要衡量一個演算法所需要的額外空間，在計算機發展的早期，計算機的存盤容量很小，所以對空間復雜度很是在乎，但是經過計算機行業的迅速發展，計算機的存盤容量已經達到了很高的程度，所以我們如今已經不需要再特別關注一個演算法的空間復雜度，
2.大o的漸進表示法
大O符號（Big O notation）：是用于描述函式漸進行為的數學符號，
用通俗的話來說就是一種估算，
eg:
F（N)=NN+N+2
用大o的漸進表示法就是O（NN）.
推導大O階方法：
1、用常數1取代運行時間中的所有加法常數，
2、在修改后的運行次數函式中，只保留最高階項，
3、如果最高階項存在且不是1，則去除與這個專案相乘的常數，得到的結果就是大O階，
eg:
void Func2(int N)
{
int count = 0;
for (int k = 0; k < 2 * N ; ++ k)
{
++count;
}
int M = 10;
while (M--)
{
++count;
}
printf("%d\n", count);
}
F(N)=2*N+10，在這里我們認為2對結果的影響不大所以時間復雜度是O(N)，
eg:
void Func3(int N, int M)
{
int count = 0;
for (int k = 0; k < M; ++ k)
{
++count;
}
for (int k = 0; k < N ; ++ k)
{
++count;
}
printf("%d\n", count);
}
由于不清楚誰對結果的影響大，所以M和N都留下，
F（N）=M+N，時間復雜度是O（M+N）.
void Func4(int N)
{
int count = 0;
for (int k = 0; k < 100; ++ k)
{
++count;
}
printf("%d\n", count);
}
F（N）=100如果回圈是常數的話，時間復雜度是O（1）.
在時間復雜度的計算中，通常假設陣列/字串長度是N，
面對不確定的情況時默認時間復雜度最壞，
求冒泡排序的時間復雜度
void BubbleSort(int* a, int n)
{
assert(a);
for (size_t end = n; end > 0; --end)
{
int exchange = 0;
for (size_t i = 1; i < end; ++i)
{
if (a[i-1] > a[i])
{
Swap(&a[i-1], &a[i]);
exchange = 1;
}
}
if (exchange == 0)
break;
}
}
F（N）=N-1+N-2+N-3+…+1
時間復雜度是一個等引數列，O(N*N)
求二分查找的時間復雜度
void BubbleSort(int* a, int n)
{
assert(a);
for (size_t end = n; end > 0; --end)
{
int exchange = 0;
for (size_t i = 1; i < end; ++i)
{
if (a[i-1] > a[i])
{
Swap(&a[i-1], &a[i]);
exchange = 1;
}
}
if (exchange == 0)
break;
}
}
最好的情況：o(1)
最壞的情況：
我們先逆著來看：122*…2=N
找了x次則/2了x次
2^x=N
x=log2^n
所以最壞的情況是O(log2^n)
遞回演算法的時間復雜度
遞回演算法的時間復雜度=遞回次數每次遞回函式中的次數，
long long Fibonacci(size_t N)
{
return N < 2 ? N : Fibonacci(N-1)+Fibonacci(N-2);
}
后面講解二叉樹的時候會著重講解，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/273721.html
標籤：其他
上一篇：Spatial-Temporal Multi-Cue Network for Continuous Sign Language Recognition