«O» большое и «o» малое (O и o) — ... используется при оценке сложности алгоритмов.
Может кто-то объяснить?
http://ru.wikipedia.org/wiki/«O»_большое_и_«o»_малое
Может кто-то объяснить?
Может кто-то объяснить?
Это не функция, а сокращённая запись характеристики других функций. Например, если погрешность
то это означает лишь, что 
где константа 
может зависеть, в принципе, от чего угодно, но только не от 
И больше никакой информации в этой записи не содержится. - ответ не мой.Прочитал статью, несмотря на то что я инженер(IVкурс), не совсем разобрался, где ты это изучаешь?
Я точню не помню как мы учили, а конспекта нету, но, примерно, так:
"о" маленькое - сокращенная запись сравнения функций. Это значит, что данная функция изменяет значения куда медленее. На словах обьяснить не могу, поэтому покажу на примере. y=x являеться "о" маленьким от y=x^4, поскольку при одних и тех же значениях аргумента, значения функции y=x^4 возрастает куда быстрее чем значения функции y=x, тоесть являеться на порядок большим. "О" большое практически тоже самое, чесно говоря отличия между ними я не знаю. Думаю понятно
П.С. Я думал это учат практически на всех технических специальностях, ибо это основы математического анализа...
"о" маленькое - сокращенная запись сравнения функций. Это значит, что данная функция изменяет значения куда медленее. На словах обьяснить не могу, поэтому покажу на примере. y=x являеться "о" маленьким от y=x^4, поскольку при одних и тех же значениях аргумента, значения функции y=x^4 возрастает куда быстрее чем значения функции y=x, тоесть являеться на порядок большим. "О" большое практически тоже самое, чесно говоря отличия между ними я не знаю. Думаю понятно
П.С. Я думал это учат практически на всех технических специальностях, ибо это основы математического анализа...
Ненене, не то... Это у меня по программированию такое.
Нужно, например, оценить сложность алгоритма X и будет оно такое:
Т(x) = O(n log n)
Тут они(поляки) называют это "временной зависимостью зависимостью", но у нас аналог - сложность алгоритма.
Может кто-то знает, как считать правильно это?
Нужно, например, оценить сложность алгоритма X и будет оно такое:
Т(x) = O(n log n)
Тут они(поляки) называют это "временной зависимостью зависимостью", но у нас аналог - сложность алгоритма.
Может кто-то знает, как считать правильно это?
Задача №1:
Время — основной параметр, характеризующий быстродействие алгоритма.
Время, затраченное на реализацию алгоритма, как функция размерности задачи называется временной сложностью алгоритма и обозначается как O[fA(n)].
Примеры:
Теорема про найкращий час сортування. Доведення:
Відомі алгоритми сортування:
Якщо я правильно зрозумів задачу і враховуючи, що 1 курс і програмування. То лише треба запрограмувати визначення розміру масиву, обчислення швидкодії для їх подальшого порівняння з іншими методами чи з іншими масивами.
Отже реалізація на С++:
Задача:
Порівняти швидкодію методів сортування вибором та сортування злиттям
для масиві розміром n i n^n.
Програмний код:
int main(int argc, char* argv[])
{
int a[],b[] i,an=10,bn,SV,SZ,SV1,SZ1;
// an-розмір масиву a,bn-розмір масиву b,SV,SV1-швидкодія(сложность алгоритма) сортування вставками масиву a i b відповідно
// SZ,SZ1-швидкодія(сложность алгоритма) сортування злиттям масиву a i b відповідно
br=pow(an,2); //-визначенн розміру масиву b на основі a згідно поставленої задачі
// може бути не відомий розмір а і тоді треба буде визначати при введені масиву
Vsort(a,an); //- викликаєм функцію сортування вставками і сорутєм масив а
Zluttya(a,an); //- викликаєм функцію сортування злиттям і сорутєм масив b
Vsort(b,bn); //- викликаєм функцію сортування вставками і сорутєм масив а
Zluttya(b,bn); //- викликаєм функцію сортування злиттям і сорутєм масив b
SV=pow(an,2); //- згідно формули визначаєм швидкодію сортування вставками на прикладі масиву а
SV1=pow(bn,2); //- згідно формули визначаєм швидкодію сортування вставками на прикладі масиву b
SZ=an*log(an); //- згідно формули визначаєм швидкодію сортування злиттям на прикладі масиву а
SZ1=bn*log(bn); //- згідно формули визначаєм швидкодію сортування злиттям на прикладі масиву b
Por=SV/SZ; //- порівнюєм отримані дані, звідсе визначемо перевагу одного алгоритма над іншим
Por1=SV1/SZ1; //- порівнюєм отримані дані, звідсе визначемо перевагу одного алгоритма над іншим
Por2=SV/SV1; //- звідси визначемо як розмір масиву впливає на швидкодію сортування вставками
Por3=SZ/SZ1; //- звідси визначемо як розмір масиву впливає на швидкодію сортування злиттям
return 0;
}
funcion Vsort(int *a[],int *n)
{
// описуєм функцію сортування вставками
}
funcion Zluttya(int *a[],int *n)
{
// описуєм функцію сортування злиттям
}
Задача №2:
Реалізація на С++:
Задача:
Программа вчитывает текст и выписывает каждое слово в отдельной строчке.
Феншуй - это когда холодильник стоит рядом с компом.
Програмний код:
Время — основной параметр, характеризующий быстродействие алгоритма.
Время, затраченное на реализацию алгоритма, как функция размерности задачи называется временной сложностью алгоритма и обозначается как O[fA(n)].
Примеры:
Теорема про найкращий час сортування. Доведення:
Відомі алгоритми сортування:
Якщо я правильно зрозумів задачу і враховуючи, що 1 курс і програмування. То лише треба запрограмувати визначення розміру масиву, обчислення швидкодії для їх подальшого порівняння з іншими методами чи з іншими масивами.
Отже реалізація на С++:
Задача:
Порівняти швидкодію методів сортування вибором та сортування злиттям
для масиві розміром n i n^n.
Програмний код:
int main(int argc, char* argv[])
{
int a[],b[] i,an=10,bn,SV,SZ,SV1,SZ1;
// an-розмір масиву a,bn-розмір масиву b,SV,SV1-швидкодія(сложность алгоритма) сортування вставками масиву a i b відповідно
// SZ,SZ1-швидкодія(сложность алгоритма) сортування злиттям масиву a i b відповідно
br=pow(an,2); //-визначенн розміру масиву b на основі a згідно поставленої задачі
// може бути не відомий розмір а і тоді треба буде визначати при введені масиву
Vsort(a,an); //- викликаєм функцію сортування вставками і сорутєм масив а
Zluttya(a,an); //- викликаєм функцію сортування злиттям і сорутєм масив b
Vsort(b,bn); //- викликаєм функцію сортування вставками і сорутєм масив а
Zluttya(b,bn); //- викликаєм функцію сортування злиттям і сорутєм масив b
SV=pow(an,2); //- згідно формули визначаєм швидкодію сортування вставками на прикладі масиву а
SV1=pow(bn,2); //- згідно формули визначаєм швидкодію сортування вставками на прикладі масиву b
SZ=an*log(an); //- згідно формули визначаєм швидкодію сортування злиттям на прикладі масиву а
SZ1=bn*log(bn); //- згідно формули визначаєм швидкодію сортування злиттям на прикладі масиву b
Por=SV/SZ; //- порівнюєм отримані дані, звідсе визначемо перевагу одного алгоритма над іншим
Por1=SV1/SZ1; //- порівнюєм отримані дані, звідсе визначемо перевагу одного алгоритма над іншим
Por2=SV/SV1; //- звідси визначемо як розмір масиву впливає на швидкодію сортування вставками
Por3=SZ/SZ1; //- звідси визначемо як розмір масиву впливає на швидкодію сортування злиттям
return 0;
}
funcion Vsort(int *a[],int *n)
{
// описуєм функцію сортування вставками
}
funcion Zluttya(int *a[],int *n)
{
// описуєм функцію сортування злиттям
}
Задача №2:
Реалізація на С++:
Задача:
Программа вчитывает текст и выписывает каждое слово в отдельной строчке.
Феншуй - это когда холодильник стоит рядом с компом.
Програмний код:
#include "stdafx.h"
#include <iostream.h>
#include <string.h>
#include <conio.h>
int main(int argc, char* argv[])
{
char a[250]="Fen-Shuj exsist when refrigerator is near computer."; int g=0,h=0,i,k,m=0,j;
k=strlen(a);
for(i=0;i<k;i++)
cout<<a[i];
cout<<"\n"<<"\n";
for(i=0;i<k;i++)
if(a[i]==' '||a[i]=='.')
{ m++;
if(m==1)
for(j=g;j<i;j++){cout<<a[j];h=i+1;}
cout<<"\n";
if(m>1)
{
for(j=g+h;j<i;j++){cout<<a[j];h=i+1;}
cout<<"\n";
}
}
cout<<"\n";
return 0;
}
#include <iostream.h>
#include <string.h>
#include <conio.h>
int main(int argc, char* argv[])
{
char a[250]="Fen-Shuj exsist when refrigerator is near computer."; int g=0,h=0,i,k,m=0,j;
k=strlen(a);
for(i=0;i<k;i++)
cout<<a[i];
cout<<"\n"<<"\n";
for(i=0;i<k;i++)
if(a[i]==' '||a[i]=='.')
{ m++;
if(m==1)
for(j=g;j<i;j++){cout<<a[j];h=i+1;}
cout<<"\n";
if(m>1)
{
for(j=g+h;j<i;j++){cout<<a[j];h=i+1;}
cout<<"\n";
}
}
cout<<"\n";
return 0;
}