Что, черт возьми, Big O
- n - размер данных
- O(f(n)) fn является функцией от n. Указывает количество инструкций, которые необходимо выполнить для запуска алгоритма, пропорциональное f(n).
- Это имеет мало общего с постоянными членами a.b.c.d. В основном это зависит от того, на каком уровне он находится.
Алгоритм A: O(n) Количество инструкций для выполнения: 10000n
Алгоритм B: O(n^2) Количество инструкций для выполнения: 10n^2
- Размер n постепенно увеличивается. Изменение количества инструкций для алгоритмов а.б.
-
Когда n больше критической точки, a должно превышать b. Это разница в величине.
-
Алгоритмы высокой сложности могут иметь указанные выше преимущества и иметь смысл при небольшом объеме данных.
- Для всех расширенных алгоритмов сортировки, когда размер данных достаточно мал, мы можем использовать сортировку вставками для оптимизации. 10%-15%. Детальная оптимизация.
-
Различная временная сложность с увеличением размера данных
соглашение
- Строго говоря, в академических кругах O (f (n)) представляет собой верхнюю границу выполнения алгоритма.
- Временная сложность алгоритма сортировки слиянием составляет O(nlogn), что также равно O(n^2).
- c.nlogn < a.n^2
- В отрасли мы используем O для представления нижней верхней границы выполнения алгоритма.
- Обычно мы не говорим, что сортировка слиянием - это O (n ^ 2)
пример
- Исполняется главная роль:
O( nlogn + n ) = O( nlogn )
O( nlogn + n^2 ) = O( n^2 )
- Приведенная выше формула требует, чтобы алгоритм работал с одним и тем же n (O(AlogA + B), O(AlogA + B^2))
- Вышеупомянутое нельзя опустить
- Проходим по графу, реализованному списком смежности:
- Временная сложность: O(V + E) V — количество вершин, а E — количество ребер.
- Плотные графы, даже полные графы. Е близко к уровню V^2.
проблема временной сложности
Имеется массив строк, и каждая строка в массиве сортируется по алфавиту, затем весь массив строк сортируется лексикографически. Временная сложность всей операции?
- n*nlogn на строку + весь массив строк: nlogn
- Путаница длины строки ошибки и длины массива
Предположим, что самая длинная строка имеет длину s; в массиве n строк
Сортировать каждую строку: O(slogs)
Отсортируйте каждую строку в массиве в алфавитном порядке: O(n*slog(s))
-
Отсортируйте весь массив строк лексикографически: O(s*nlog(n))
- Объяснение: Для понимания временной сложности алгоритма сортировки:
- nlogn — количество сравнений. Для сортировки целочисленного массива требуется только nlogn сравнений.
- Потому что сравнение между двумя целыми числами равно O(1). Сравнение двух строк не является одним и тем же O (s).
-
O(nslog(s)) + O(snlog(n)) = O( nslogs + snlogn )= O( ns(logs+logn) )
-
Строковые массивы сортируются лексикографически. При сравнении nlogn раз каждое сравнение требует O(s) временной сложности.
В некоторых случаях алгоритмическая сложность зависит от варианта использования.
Алгоритм сортировки вставками O (n ^ 2)
- Худший случай: O(n^2)
- Лучший случай: O(n): почти заказано
- Средний случай: O(n^2)
Алгоритм быстрой сортировки O(nlogn)
- В худшем случае: O (n ^ 2) не случайно. аккуратный
- Лучший случай: O(nlogn) рандомизация точек калибровки
- Средний случай: O(nlogn)
Строгие алгоритмы — лучшее среднее худшее. Мы часто ориентируемся на большинство.
В крайнем случае достаточно.
Концепция масштаба данных
Выполнить сортировку выбора по данным 10 ^ 5, результат - компьютерная пауза?
#include <iostream>
#include <cmath>
#include <ctime>
using namespace std;
int main() {
// 数据规模每次增大10倍进行测试
// 有兴趣的同学也可以试验一下数据规模每次增大2倍哦:)
for( int x = 1 ; x <= 9 ; x ++ ){
int n = pow(10, x);
clock_t startTime = clock();
long long sum = 0;
for( int i = 0 ; i < n ; i ++ )
sum += i;
clock_t endTime = clock();
cout << "sum = " << sum << endl;
cout << "10^" << x << " : "
<< double(endTime - startTime)/CLOCKS_PER_SEC
<< " s" << endl << endl;
}
return 0;
}
результат операции
sum = 45
10^1 : 2e-06 s
sum = 4950
10^2 : 1e-06 s
sum = 499500
10^3 : 4e-06 s
sum = 49995000
10^4 : 2.9e-05 s
sum = 4999950000
10^5 : 0.000305 s
sum = 499999500000
10^6 : 0.003049 s
sum = 49999995000000
10^7 : 0.029234 s
sum = 4999999950000000
10^8 : 0.308056 s
sum = 499999999500000000
10^9 : 2.98528 s
Если вы хотите решить проблему в течение 1 с
- Алгоритмы O(n^2) могут обрабатывать данные порядка 10^4;
- Алгоритмы O(n) могут обрабатывать данные порядка 10^8;
- Алгоритм O (nlogn) может обрабатывать около 10 ^ 7 уровней данных.
Поскольку операция, которую мы только что сделали, очень проста, это простое сложение. Так что это нормально немного занижать, а потом делить на 10
космическая сложность
- Откройте дополнительный вспомогательный массив: O(n)
- Откройте дополнительный вспомогательный двумерный массив: O(n^2)
- Мультиоткрытое постоянное пространство: O(1): сортировка массива на месте
- Рекурсивные вызовы имеют стоимость места:
- Функция помещается в системный стек перед рекурсивным вызовом.
Общий анализ сложности
O(1)
Масштаб данных не меняется
// O(1)
void swapTwoInts( int &a , int &b ){
int temp = a;
a = b;
b = temp;
return;
}
O(n)
Число операций цикла равно c.n. c - константа, которая не обязательно является числом больше 1
// O(n) Time Complexity
int sum( int n ){
int ret = 0;
for( int i = 0 ; i <= n ; i ++ )
ret += i;
return ret;
}
O(n)
Количество петель 1/2*n раз
Переворот струны. abc-cba Первый и последний. 2-й и предпоследний
Обмен на полпути через сканирование: 1/2 * n операций обмена: O (n)
void reverse( string &s ){
int n = s.size();
for( int i = 0 ; i < n/2 ; i ++ )
swap( s[i] , s[n-1-i] );
return;
}
O(n^2)
Сортировка выбором. О (п ^ 2)
Двойная петля: сначала повторять до n. Второй тяжелый n. Оба +1.
Количество выполняемых инструкций пропорционально n^2.
i = 0;j выполняет n-1 арифметическое суммирование
(n-1) + (n-2) + (n-3) + … + 0
= (0+n-1)*n/2
= (1/2)n*(n-1)
= 1/2*n^2 - 1/2*n
= O(n^2)
// O(n^2) Time Complexity
void selectionSort(int arr[], int n){
for(int i = 0 ; i < n ; i ++){
int minIndex = i;
for( int j = i + 1 ; j < n ; j ++ )
if( arr[j] < arr[minIndex] )
minIndex = j;
swap( arr[i] , arr[minIndex] );
}
}
30n основных операций: O(n)
Поскольку цикл второго слоя фиксирован и не зависит от n.
// O(n) Time Complexity
void printInformation(int n){
for( int i = 1 ; i <= n ; i ++ )
for( int j = 1 ; j <= 30 ; j ++ )
cout<<"Class "<<i<<" - "<<"No. "<<j<<endl;
return;
}
o(logn)
Найдите средний элемент отсортированного массива, чтобы определить отношение между элементом и средним элементом.
Если ничего не найдено, половину элементов можно выбросить.
бинарный поиск
// O(logn) Time Complexity
int binarySearch(int arr[], int n, int target){
int l = 0, r = n-1;
while( l <= r ){
int mid = l + (r-l)/2;
if( arr[mid] == target ) return mid;
if( arr[mid] > target ) r = mid - 1;
else l = mid + 1;
}
return -1;
}
O(logn)
После нескольких операций «деления на 10» n равно 0?
log10n = O(logn)
Разделите на 10 каждый раз в цикле while до конца 0.
обратная(ые) сложность: 1/2 n операций подкачки. Количество битов в строке s, соответствующее n.
string intToString( int num ){
string s = "";
string sign = "+";
if( num < 0 ){
num = -num;
sign = "-";
}
while( num ){
s += '0' + num%10;
num /= 10;
}
if( s == "" )
s = "0";
reverse(s);
if( sign == "-" )
return sign + s;
else
return s;
}
O(nlogn)
Второй цикл n
Первый размер+=размер умножается на 2.log2n
// O(nlogn)
void hello(int n){
for( int sz = 1 ; sz < n ; sz += sz )
for( int i = 1 ; i < n ; i ++ )
cout<<"Hello, Algorithm!"<<endl;
}
O(sqrt(n))
x идет от n до конца корня n
// O(sqrt(n)) Time Complexity
bool isPrime( int num ){
for( int x = 2 ; x*x <= num ; x ++ )
if( num%x == 0 )
return false;
return true;
}
bool isPrime2( int num ){
if( num <= 1 ) return false;
if( num == 2 ) return true;
if( num%2 == 0 ) return false;
for( int x = 3 ; x*x <= num ; x += 2 )
if( num%x == 0 )
return false;
return true;
}
эксперимент сложности.
Мы думали, что написали алгоритм O(nlogn), но действительно ли это алгоритм O(n^2)?
Если вы хотите решить проблему за 1с:
- Алгоритмы O(n2) могут обрабатывать данные примерно 10^4 уровней;
- Алгоритмы O(n) могут обрабатывать данные порядка 10^8;
- Алгоритм O (nlogn) может обрабатывать около 10 ^ 7 уровней данных.
Предыдущий постоянный разрыв может быть большим.
Экспериментируйте и наблюдайте за тенденциями:
Каждый раз увеличивайте размер данных в два раза и смотрите изменение во времени
Четыре алгоритма разной сложности.
namespace MyAlgorithmTester{
// O(logN)
int binarySearch(int arr[], int n, int target){
int l = 0, r = n-1;
while( l <= r ){
int mid = l + (r-l)/2;
if( arr[mid] == target ) return mid;
if( arr[mid] > target ) r = mid - 1;
else l = mid + 1;
}
return -1;
}
// O(N)
int findMax( int arr[], int n ){
assert( n > 0 );
int res = arr[0];
for( int i = 1 ; i < n ; i ++ )
if( arr[i] > res )
res = arr[i];
return res;
}
// O(NlogN) 自底向上
void __merge(int arr[], int l, int mid, int r, int aux[]){
for(int i = l ; i <= r ; i ++)
aux[i] = arr[i];
int i = l, j = mid+1;
for( int k = l ; k <= r; k ++ ){
if( i > mid ) { arr[k] = aux[j]; j ++;}
else if( j > r ){ arr[k] = aux[i]; i ++;}
else if( aux[i] < aux[j] ){ arr[k] = aux[i]; i ++;}
else { arr[k] = aux[j]; j ++;}
}
}
void mergeSort( int arr[], int n ){
int *aux = new int[n];
for( int i = 0 ; i < n ; i ++ )
aux[i] = arr[i];
for( int sz = 1; sz < n ; sz += sz )
for( int i = 0 ; i < n ; i += sz+sz )
__merge(arr, i, i+sz-1, min(i+sz+sz-1,n-1), aux );
delete[] aux;
return;
}
// O(N^2) 选择排序
void selectionSort( int arr[], int n ){
for(int i = 0 ; i < n ; i ++){
int minIndex = i;
for( int j = i + 1 ; j < n ; j ++ )
if( arr[j] < arr[minIndex] )
minIndex = j;
swap( arr[i] , arr[minIndex] );
}
return;
}
}
Код для создания тестового примера:
namespace MyUtil {
int *generateRandomArray(int n, int rangeL, int rangeR) {
assert( n > 0 && rangeL <= rangeR );
int *arr = new int[n];
srand(time(NULL));
for (int i = 0; i < n; i++)
arr[i] = rand() % (rangeR - rangeL + 1) + rangeL;
return arr;
}
int *generateOrderedArray(int n) {
assert( n > 0 );
int *arr = new int[n];
for (int i = 0; i < n; i++)
arr[i] = i;
return arr;
}
}
Уровень теста O(n)?
int main() {
// 数据规模倍乘测试findMax
// O(n)
cout<<"Test for findMax:"<<endl;
for( int i = 10 ; i <= 26 ; i ++ ){
int n = pow(2,i);
int *arr = MyUtil::generateRandomArray(n, 0, 100000000);
clock_t startTime = clock();
MyAlgorithmTester::findMax(arr, n);
clock_t endTime = clock();
cout<<"data size 2^"<<i<<" = "<<n<<"\t";
cout<<"Time cost: "<<double(endTime - startTime)/CLOCKS_PER_SEC<<endl;
delete[] arr;
}
return 0;
}
результат операции:
Test for findMax:
data size 2^10 = 1024 Time cost: 5e-06 s
data size 2^11 = 2048 Time cost: 7e-06 s
data size 2^12 = 4096 Time cost: 1.2e-05 s
data size 2^13 = 8192 Time cost: 2.5e-05 s
data size 2^14 = 16384 Time cost: 4.7e-05 s
data size 2^15 = 32768 Time cost: 9.2e-05 s
data size 2^16 = 65536 Time cost: 0.000169 s
data size 2^17 = 131072 Time cost: 0.000431 s
data size 2^18 = 262144 Time cost: 0.000737 s
data size 2^19 = 524288 Time cost: 0.001325 s
data size 2^20 = 1048576 Time cost: 0.002489 s
data size 2^21 = 2097152 Time cost: 0.005739 s
data size 2^22 = 4194304 Time cost: 0.011373 s
data size 2^23 = 8388608 Time cost: 0.019566 s
data size 2^24 = 16777216 Time cost: 0.040289 s
data size 2^25 = 33554432 Time cost: 0.095169 s
data size 2^26 = 67108864 Time cost: 0.201682 s
data size 2^27 = 134217728 Time cost: 0.330673 s
data size 2^28 = 268435456 Time cost: 0.750136 s
n увеличилось втрое. Время также примерно удваивается, поэтому алгоритм имеет уровень O(n).
Является ли тест O (n ^ 2)
int main() {
// 数据规模倍乘测试selectionSort
// O(n^2)
cout<<"Test for selectionSort:"<<endl;
for( int i = 10 ; i <= 15 ; i ++ ){
int n = pow(2,i);
int *arr = MyUtil::generateRandomArray(n, 0, 100000000);
clock_t startTime = clock();
MyAlgorithmTester::selectionSort(arr,n);
clock_t endTime = clock();
cout<<"data size 2^"<<i<<" = "<<n<<"\t";
cout<<"Time cost: "<<double(endTime - startTime)/CLOCKS_PER_SEC<<endl;
delete[] arr;
}
return 0;
}
Результат работы: около 4 раз
Test for Selection Sort:
data size 2^10 = 1024 Time cost: 0.001581 s
data size 2^11 = 2048 Time cost: 0.006221 s
data size 2^12 = 4096 Time cost: 0.021913 s
data size 2^13 = 8192 Time cost: 0.081103 s
data size 2^14 = 16384 Time cost: 0.323263 s
data size 2^15 = 32768 Time cost: 1.32474 s
data size 2^16 = 65536 Time cost: 5.19642 s
Количество данных n увеличивается в 2 раза. Время увеличилось в 4 раза.
Является ли тест O (logN)
int main() {
// 数据规模倍乘测试binarySearch
// O(logn)
cout<<"Test for binarySearch:"<<endl;
for( int i = 10 ; i <= 28 ; i ++ ){
int n = pow(2,i);
int *arr = MyUtil::generateOrderedArray(n);
clock_t startTime = clock();
MyAlgorithmTester::binarySearch(arr,n,0);
clock_t endTime = clock();
cout<<"data size 2^"<<i<<" = "<<n<<"\t";
cout<<"Time cost: "<<double(endTime - startTime)/CLOCKS_PER_SEC<<endl;
delete[] arr;
}
return 0;
}
тест на сложность
log2N / logN
= (log2 + logN)/logN
= 1 + log2/logN
Когда размер данных удваивается. Эффективность работы увеличивается в 1. раз.
результат операции:
Test for Binary Search:
data size 2^10 = 1024 Time cost: 1e-06 s
data size 2^11 = 2048 Time cost: 0 s
data size 2^12 = 4096 Time cost: 0 s
data size 2^13 = 8192 Time cost: 2e-06 s
data size 2^14 = 16384 Time cost: 1e-06 s
data size 2^15 = 32768 Time cost: 1e-06 s
data size 2^16 = 65536 Time cost: 1e-06 s
data size 2^17 = 131072 Time cost: 2e-06 s
data size 2^18 = 262144 Time cost: 3e-06 s
data size 2^19 = 524288 Time cost: 1e-06 s
data size 2^20 = 1048576 Time cost: 4e-06 s
data size 2^21 = 2097152 Time cost: 3e-06 s
data size 2^22 = 4194304 Time cost: 3e-06 s
data size 2^23 = 8388608 Time cost: 4e-06 s
data size 2^24 = 16777216 Time cost: 4e-06 s
data size 2^25 = 33554432 Time cost: 1.2e-05 s
data size 2^26 = 67108864 Time cost: 9e-06 s
data size 2^27 = 134217728 Time cost: 1.1e-05 s
data size 2^28 = 268435456 Time cost: 2.4e-05 s
Текущие результаты, небольшие изменения
Преобразование последовательного поиска в бинарный поиск, что значительно повышает эффективность
Тест O(NlogN)
Это примерно то же самое, что O(N)
int main() {
// 数据规模倍乘测试mergeSort
// O(nlogn)
cout<<"Test for mergeSort:"<<endl;
for( int i = 10 ; i <= 24 ; i ++ ){
int n = pow(2,i);
int *arr = MyUtil::generateRandomArray(n,0,1<<30);
clock_t startTime = clock();
MyAlgorithmTester::mergeSort(arr,n);
clock_t endTime = clock();
cout<<"data size 2^"<<i<<" = "<<n<<"\t";
cout<<"Time cost: "<<double(endTime - startTime)/CLOCKS_PER_SEC<<endl;
delete[] arr;
}
return 0;
}
результат операции:
Test for Merge Sort:
data size 2^10 = 1024 Time cost: 0.000143 s
data size 2^11 = 2048 Time cost: 0.000325 s
data size 2^12 = 4096 Time cost: 0.000977 s
data size 2^13 = 8192 Time cost: 0.001918 s
data size 2^14 = 16384 Time cost: 0.003678 s
data size 2^15 = 32768 Time cost: 0.007635 s
data size 2^16 = 65536 Time cost: 0.015768 s
data size 2^17 = 131072 Time cost: 0.034462 s
data size 2^18 = 262144 Time cost: 0.069586 s
data size 2^19 = 524288 Time cost: 0.136214 s
data size 2^20 = 1048576 Time cost: 0.294626 s
data size 2^21 = 2097152 Time cost: 0.619943 s
data size 2^22 = 4194304 Time cost: 1.37317 s
data size 2^23 = 8388608 Time cost: 2.73054 s
data size 2^24 = 16777216 Time cost: 5.60827 s
примерно вдвое больше
Анализ сложности рекурсивных алгоритмов
- Функция, которая не является рекурсивной, должна иметь значение O(nlogn)!
Рекурсивная реализация бинарного поиска:
Левая или правая половина. Независимо от того, какую сторону вы выберете, сделайте это только один раз
Каждый халвинг, логгируется глубина рекурсивных вызовов, а сложность обработки задачи O(1)
// binarySearch
int binarySearch(int arr[], int l, int r, int target){
if( l > r )
return -1;
int mid = l + (r-l)/2;
if( arr[mid] == target )
return mid;
else if( arr[mid] > target )
return binarySearch(arr, l, mid-1, target);
else
return binarySearch(arr, mid+1, r, target);
}
Если в рекурсивной функции делается только один рекурсивный вызов,
Глубина рекурсии — это глубина;
В каждой рекурсивной функции временная сложность равна T;
Тогда общая временная сложность равна O(T * depth)
Рекурсивная реализация суммирования
Глубина рекурсии: n
Временная сложность: O(n)
// sum
int sum( int n ){
assert( n >= 0 );
if( n == 0 )
return 0;
return n + sum(n-1);
}
Вычислите степень x, возведенную в n-ю степень
// pow2
double pow( double x, int n ){
assert( n >= 0 );
if( n == 0 )
return 1.0;
double t = pow(x, n/2);
//奇数
if( n%2 )
return x*t*t;
return t*t;
}
Глубина рекурсии: logn
Временная сложность: O(logn)
сделать несколько рекурсивных вызовов в рекурсии
Глубина дерева рекурсии N
2^0 + 2^1 + 2^2 + 2^3 + … + 2^n
= 2n+1 - 1
= O(2^n)
Экспоненциальный алгоритм: очень медленный. n около 20. 30 очень медленно Операция обрезки: динамическое программирование. Искусственный интеллект: деревья поиска
// f
int f(int n){
assert( n >= 0 );
if( n == 0 )
return 1;
return f(n-1) + f(n-1);
}
Сортировка слиянием n = 8
Глубина дерева logN Когда n равно 8, количество слоев равно 3. Масштаб данных, обрабатываемых каждым слоем, становится все меньше и меньше
Один разделен на лог-слои. Общий размер суммы каждого слоя по-прежнему n
// mergeSort
void mergeSort(int arr[], int l, int r){
if( l >= r )
return;
int mid = (l+r)/2;
mergeSort(arr, l, mid);
mergeSort(arr, mid+1, r);
merge(arr, l, mid, r);
}
Анализ амортизированного времени
Алгоритм относительно сложен, но он используется для облегчения других операций.
Высшие будут равномерно распределены в целом.
Динамический массив (вектор)
template <typename T>
class MyVector{
private:
T* data;
int size; // 存储数组中的元素个数
int capacity; // 存储数组中可以容纳的最大的元素个数
// O(n)：一重循环。
void resize(int newCapacity){
assert( newCapacity >= size );
T *newData = new T[newCapacity];
for( int i = 0 ; i < size ; i ++ )
newData[i] = data[i];
delete[] data;
data = newData;
capacity = newCapacity;
}
public:
MyVector(){
data = new T[100];
size = 0;
capacity = 100;
}
~MyVector(){
delete[] data;
}
// Average: O(1)
void push_back(T e){
//动态数组
if( size == capacity )
resize( 2* capacity );
data[size++] = e;
}
// O(1)
T pop_back(){
assert( size > 0 );
size --;
//size是从0开始的。也就是0号索引size为1.
//所以要拿到最后一个元素，就得size-1
return data[size];
}
};
разделить поровну
n+1-й раз будет стоить O(n), но амортизирует это n по сравнению с предыдущими n операциями. То есть становится O(2)
Это по-прежнему постоянный уровень O (1).
resize является условным, не вызывается каждый раз.
int main() {
for( int i = 10 ; i <= 26 ; i ++ ){
int n = pow(2,i);
clock_t startTime = clock();
MyVector<int> vec;
for( int i = 0 ; i < n ; i ++ ){
vec.push_back(i);
}
clock_t endTime = clock();
cout<<n<<" operations: \t";
cout<<double(endTime - startTime)/CLOCKS_PER_SEC<<" s"<<endl;
}
return 0;
}
1024 operations: 2.5e-05 s
2048 operations: 2.9e-05 s
4096 operations: 7.4e-05 s
8192 operations: 0.000154 s
16384 operations: 0.000265 s
32768 operations: 0.000391 s
65536 operations: 0.001008 s
131072 operations: 0.002006 s
262144 operations: 0.003863 s
524288 operations: 0.005842 s
1048576 operations: 0.014672 s
2097152 operations: 0.029367 s
4194304 operations: 0.06675 s
8388608 operations: 0.124446 s
16777216 operations: 0.240025 s
33554432 operations: 0.486061 s
67108864 operations: 0.960224 s
В основном встречайте отношения 2 раза
Удаление элементов уменьшает пространство.
Временная сложность каждого обычного удаления составляет O(1)
Осталось только n. На этот раз изменение размера n удаляет этот элемент до 1
Повторение этого процесса не может быть амортизировано, а сложность равна O(n).
Когда количество элементов равно 1/4 емкости массива, измените размер, оставив место для дополнительных элементов.
template <typename T>
class MyVector{
private:
T* data;
int size; // 存储数组中的元素个数
int capacity; // 存储数组中可以容纳的最大的元素个数
// O(n)
void resize(int newCapacity){
assert( newCapacity >= size );
T *newData = new T[newCapacity];
for( int i = 0 ; i < size ; i ++ )
newData[i] = data[i];
delete[] data;
data = newData;
capacity = newCapacity;
}
public:
MyVector(){
data = new T[100];
size = 0;
capacity = 100;
}
~MyVector(){
delete[] data;
}
// Average: O(1)
void push_back(T e){
if( size == capacity )
resize( 2* capacity );
data[size++] = e;
}
// Average: O(1)
T pop_back(){
assert( size > 0 );
T ret = data[size-1];
size --;
if( size == capacity/4 )
resize( capacity/2 );
//resize之后会把data[size]元素抹掉
return ret;
}
};
результат операции
2048 operations: 4.3e-05 s
4096 operations: 6.3e-05 s
8192 operations: 0.000107 s
16384 operations: 0.000316 s
32768 operations: 0.000573 s
65536 operations: 0.001344 s
131072 operations: 0.001995 s
262144 operations: 0.004102 s
524288 operations: 0.008599 s
1048576 operations: 0.014714 s
2097152 operations: 0.027181 s
4194304 operations: 0.063136 s
8388608 operations: 0.126046 s
16777216 operations: 0.242574 s
33554432 operations: 0.456381 s
67108864 operations: 0.96618 s
134217728 operations: 1.76422 s
Амортизированная сложность
- динамический массив
- динамический стек
- динамическая очередь
------------------------- Великолепная разделительная линия --------------------
Друзья, которые прочитали это, могут нажать «Нравится» / «Подписаться», ваша поддержка — самая большая поддержка для меня.
личный блогСтек томатной технологииа такжеДомашняя страница Наггетс
Если вы хотите узнать больше, обратите внимание на мой публичный аккаунт WeChat: Tomato Technology Stack.