प्रौद्योगिकी साझेदारी

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

1. एल्गोरिदमस्य दक्षता

एकमेव एल्गोरिदम् समस्यां पूर्णं कर्तुं अनेकाः उपायाः पद्धतयः च सन्ति अन्तिमपरिणामः समानः सम्यक् च भवति, परन्तु कार्यक्षमता भिन्ना भवितुम् अर्हति ।
यथा एकस्मात् स्थानात् आरभ्य अन्यस्मिन् स्थाने आगत्य तत्र गन्तुं मार्गेषु विमानं, रेलयानं, निजीकारः... परन्तु गृहीतः समयः भिन्नः अर्थव्यवस्था अपि भिन्ना अस्ति।

1. जटिलतायाः अवधारणा

एल्गोरिदम् एक्जीक्यूटिव प्रोग्राम् इत्यस्मिन् लिखितस्य अनन्तरं तस्य चालनार्थं समयसंसाधनानाम्, स्थानस्य (स्मृति) संसाधनस्य च आवश्यकता भवति । अतः एल्गोरिदमस्य गुणवत्ता सामान्यतया द्वयोः आयामयोः माप्यते : कालः अन्तरिक्षः च, यथा कालजटिलता, अन्तरिक्षजटिलता च ।
समयजटिलता मुख्यतया एल्गोरिदम् कियत् शीघ्रं चालयति इति मापयति, यदा तु अन्तरिक्षजटिलता मुख्यतया एल्गोरिदम् चालयितुं आवश्यकं अतिरिक्तं स्थानं मापयति ।
सङ्गणकविकासस्य आरम्भिकाले सङ्गणकानां भण्डारणक्षमता अत्यल्पा आसीत् । अतः वयं अन्तरिक्षजटिलतायाः विषये बहु चिन्तयामः। परन्तु सङ्गणक-उद्योगस्य तीव्र-विकासानन्तरं सङ्गणकानां भण्डारण-क्षमता अतीव उच्चस्तरं प्राप्तवती अस्ति । अतः अधुना अस्माभिः एल्गोरिदम् इत्यस्य अन्तरिक्षजटिलतायाः विषये विशेषं ध्यानं दातुं आवश्यकता नास्ति ।

2. जटिलतायाः महत्त्वम्

यदा अहं केचन क्रीडाः क्रीडामि तदा मम दूरभाषः यदा अहं केचन क्रीडाः क्रीडामि तदा अतीव उष्णः भविष्यति, तथा च केचन क्रीडाः उष्णाः न भविष्यन्ति यदि अहं तान् क्रीडामि, यत् जटिलतायाः अविभाज्यम् अस्ति मम दूरभाषः सरलं एल्गोरिदम् चालयति तथा च सः शीघ्रं चालयति, परन्तु तत् चालयितुं जटिलं भवति, समयस्य न्यूनतया उपयोगः भवति इति सुनिश्चित्य, पूर्णशक्तिः सक्षमा भवितुमर्हति, अतः तत् उष्णं भविष्यति ।

2. कालजटिलता

परिभाषा : सङ्गणकविज्ञाने एल्गोरिदमस्य समयजटिलता एकं कार्यात्मकं सूत्रं T(N) भवति, यत् एल्गोरिदमस्य चालनसमयस्य परिमाणात्मकरूपेण वर्णनं करोति समयजटिलता कार्यक्रमस्य समयदक्षतां मापयति, अतः कार्यक्रमस्य चालनसमयस्य गणना किमर्थं न भवति?

• यतो हि कार्यक्रमस्य चालनसमयः संकलनवातावरणस्य चालनयन्त्रस्य च विन्यासेन सह सम्बद्धः भवति, उदाहरणार्थं यदि एल्गोरिदम् कार्यक्रमः पुरातनेन संकलकेन सह संकलितः अथवा नूतनेन संकलकेन सह संकलितः भवति तर्हि एकस्मिन् यन्त्रे चालनसमयः भिन्नः भविष्यति
• एकस्मिन् एव एल्गोरिदम् प्रोग्रामे पुरातनं न्यूनविन्यासयन्त्रं नूतनं उच्चविन्यासयन्त्रं च उपयुज्य भिन्नाः चालनसमयाः सन्ति ।
• तथा च कार्यक्रमस्य लेखनानन्तरं एव समयस्य परीक्षणं कर्तुं शक्यते, न तु कार्यक्रमस्य लेखनात् पूर्वं सैद्धान्तिकचिन्तनस्य माध्यमेन गणनां मूल्याङ्कनं च कर्तुं शक्यते।

अतः एल्गोरिदम् इत्यस्य समयनियुक्तिपदवीयाः न्याये एल्गोरिदम् निष्पादयितुं समयः न विचार्यते, केवलं निष्पादितनिर्देशानां संख्या एव विचार्यते

विषय:

// 请计算⼀下Func1中++count语句总共执⾏了多少
次？
void Func1(int N)
{
	int count = 0;
	for (int i = 0; i < N ; ++ i)
{
	for (int j = 0; j < N ; ++ j)
	{
		++count;
	}
} 
	for (int k = 0; k < 2 * N ; ++ k)
	{
		++count;
	}
	int M = 10;
	while (M--)
	{
		++count;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

अवलोकनद्वारा : १.
Func1 द्वारा कृतानां मूलभूतक्रियाणां संख्या:
त(न)=न²+ २*न + १०

व्यवहारे यदा वयं समयजटिलतां गणयामः तदा वयं प्रोग्रामस्य सटीकं निष्पादनसङ्ख्यां न गणयामः (प्रोग्राम कोडस्य भिन्नवाक्येषु संकलितनिर्देशानां भिन्नाः संख्याः भविष्यन्ति (यथा) this), निष्पादनानां सटीकसङ्ख्यायाः गणना अल्पं महत्त्वं भवति, यतः वयं केवलं समयजटिलतायाः गणनायां एल्गोरिदम् प्रोग्रामस्य वृद्धिस्तरस्य तुलनां कर्तुम् इच्छामः, अर्थात् T(N) इत्यस्मिन् अन्तरं यदा N निरन्तरं वर्धते उपरि दृष्टवन्तः यत् स्थिरांकानाम् निम्न-क्रमपदानां च परिणामेषु अल्पः प्रभावः भवति यदा N निरन्तरं वर्धते, अतः अस्माकं केवलं अनुमानितसङ्ख्यायाः गणनायाः आवश्यकता वर्तते यत् कार्यक्रमः परिमाणस्य क्रमं वर्धयितुं प्रतिनिधित्वं कर्तुं शक्नोति जटिलतायाः अभिव्यक्तिः अस्ति usually used Big O’s asymptotic notation इत्यस्य उपयोगं कुर्वन्तु ।

3. अन्तरिक्षजटिलता

अन्तरिक्षजटिलता अपि गणितीयव्यञ्जनम् अस्ति, यत् एल्गोरिदमस्य संचालनकाले एल्गोरिदम् इत्यस्य आवश्यकतायाः कारणेन अस्थायीरूपेण आवंटितं अतिरिक्तं स्थानं भवति
अन्तरिक्षजटिलता न भवति यत् कार्यक्रमः कियत् बाइट् स्थानं गृह्णाति यतः सामान्यपरिस्थितौ प्रत्येकस्य वस्तुनः आकारः बहु भिन्नः न भविष्यति, अतः स्थानजटिलता चरसङ्ख्यायाः आधारेण गण्यते
अन्तरिक्षजटिलतागणनानियमाः मूलतः व्यावहारिकजटिलतायाः सदृशाः सन्ति, तथा च Big O असममितसंकेतनस्य अपि उपयोगः भवति ।
नोट्: यदा फंक्शन् चालितं भवति तदा आवश्यकं स्टैक् स्पेस (पैरामीटर्स्, स्थानीयचराः, केचन रजिस्टर् सूचना इत्यादयः) संकलनस्य समये निर्धारितः अस्ति, अतः स्पेस जटिलता मुख्यतया रनटाइम् इत्यस्य समये फंक्शन् द्वारा स्पष्टतया प्रयुक्तेन अतिरिक्त स्पेस इत्यनेन निर्धारिता भवति । निश्चयेन
वर्तमानसङ्गणकविकासे अन्तरिक्षं प्रमुखं विचारणीयं नास्ति, परन्तु अत्यधिकं अपव्ययस्य परिहारः अवश्यं करणीयः ।

4. बिग ओ’s असममितप्रतिपादन

Big O संकेतनम् : कार्याणां असममितव्यवहारस्य वर्णनार्थं प्रयुक्तं गणितीयं चिह्नम् अस्ति ।
बिग ओ असममितसंकेतनं प्रति धक्कायितुं नियमाः : १.

• 1. कालजटिलता कार्यसूत्रे T(N) केवलं उच्चतमक्रमपदानि एव अवशिष्यन्ते, निम्नक्रमपदानि च निष्कासितानि भवन्ति, यतः यदा N निरन्तरं वर्धते तदा
  परिणामेषु निम्नक्रमपदानां प्रभावः लघुतरः भवति, यदा N अनन्तः भवति तदा तेषां अवहेलना कर्तुं शक्यते ।
• 2. यदि उच्चतमक्रमपदं विद्यते न तु 1 तर्हि अस्य पदस्य नित्यगुणकं निष्कासयन्तु, यतः यथा यथा N वर्धते तथा तथा अयं गुणांकः
  परिणामेषु प्रभावः लघुः लघुः भवति, यदा N अनन्तः भवति तदा तस्य अवहेलना कर्तुं शक्यते ।
• 3. यदि T(N) मध्ये N-सम्बद्धाः वस्तूनि न सन्ति अपितु केवलं नित्यवस्तूनि सन्ति तर्हि सर्वाणि योजकनित्यं नित्यं 1 इत्यनेन प्रतिस्थापयन्तु ।

दुर्भाग्यपूर्णः प्रकरणः: कस्यापि निवेशस्य आकारस्य अधिकतमं धावनसङ्ख्या (उपरि सीमा)
औसतप्रकरणम् : कस्यापि इनपुट् आकारस्य कृते अपेक्षितधावनसङ्ख्या
सर्वोत्तमः प्रकरणः : कस्यापि इनपुट् आकारस्य कृते न्यूनतमं रनसङ्ख्या (निम्नसीमा)
व्यवहारे बिग ओ इत्यस्य असममितप्रतिपादनं सामान्यतया एल्गोरिदमस्य उपरितनसीमायां केन्द्रीक्रियते, यत् सर्वाधिकं दुष्टं संचालनस्थितिः अस्ति ।

5. कम्प्यूटेशनल जटिलता प्रकरण

1. Func1 फंक्शन् इत्यस्य जटिलतायाः गणनां कुर्वन्तु

void Func1(int N)
{
	int count = 0;
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			++count;
		}
	} 
	for (int k = 0; k < 2 * N; ++k)
	{
		++count;
	} 
	int M = 10;
	while (M--)
	{
		++count;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

कालजटिलता : १.

एकवारं चालितं कोडं परित्यजन्तु, यथा count=0, एषः कोडः ।
चालनसमये महत् प्रभावं जनयन्तः कोडनिष्पादनानां संख्यां स्थापयन्तु
प्रथमस्य पाशस्य निष्पादनानां संख्या N इत्यस्य द्विगुणपाशस्य निष्पादनम् अस्तिन॰
द्वितीयः लूप् लूप् निष्पादनसमयानां स्तरः अस्ति 2न॰
तृतीयचक्रं १० गुणा भवति
निष्पादनसङ्ख्यायाः योगः T(N)=N भवति²+२*न+१०
बिग ओ समयजटिलतां प्रतिनिधियति, लघुप्रभावं परित्यज्य सीमां गृह्णाति
इत्युपरि²)

अन्तरिक्षजटिलता : १.

Func1 फंक्शन् स्पेस इत्यस्य आकारस्य कृते प्रवर्तते यथा, int count = 0, इदं int प्रकारस्य स्पेस आकारस्य कृते अपि प्रवर्तते ।
एतौ द्वौ रिक्तौ अपि अतिरिक्तं अनुप्रयोगस्थानं विना लूप् मध्ये उपयुज्यते ।
अनुप्रयोगस्थानस्य आकारः नित्यः भवति
बिग ओ इत्यस्मिन् व्यक्ता अन्तरिक्षजटिलता अस्ति : १.
ओ(१) ९.

2. Fun2 इत्यस्य समयजटिलतायाः गणनां कुर्वन्तु

void Func2(int N)
{
	int count = 0;
	for (int k = 0; k < 2 * N; ++k)
	{
		++count;
	} 
	int M = 10;
	while (M--)
	{
		++count;
	} 
	printf("%dn", count);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

कालजटिलता : १.

कोडस्य चालनस्य संख्या प्रथमपाशस्य अपेक्षया अधिका भवति, यत् N*2 अस्ति ।
द्वितीयः पाशः १० वारं चाल्यते
समयजटिलतायाः प्रतिनिधित्वार्थं बृहत् O इत्यस्य उपयोगं कुर्वन्तु बृहत्तमः प्रभावः 2*N अस्ति ।
इत्युपरि)

3. Func3 इत्यस्य समयजटिलतायाः गणनां कुर्वन्तु

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("%dn", count);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

कालजटिलता

अज्ञातद्वयं भवति, अधिकः प्रभावः पाशद्वये भवति
प्रथमः पाशः M वारं चालयति
द्वितीयः पाशः N वारं चालयति
अज्ञातसङ्ख्या भवितुमर्हति अहं न निश्चितः यत् कः बृहत्तरः कः लघुः इति ।
ओ(म+न) ९.

4. Func4 इत्यस्य समयजटिलतायाः गणनां कुर्वन्तु

void Func4(int N)
{
	int count = 0;
	for (int k = 0; k < 100; ++k)
	{
		++count;
	}
	printf("%dn", count);
}
1
2
3
4
5
6
7
8
9

कालजटिलता : १.

अत्र सर्वाधिकं प्रभावः चक्रं भवति
लूप् इत्यस्य चालनस्य संख्या १०० भवति
इति नियतनित्यम्
ओ(१) ९.

5. strchr इत्यस्य समयजटिलतायाः गणनां कुर्वन्तु

const char* strchr(const char* str, int character)
{
	const char* p_begin = str;
	while (*p_begin != character)
	{
		if(*p_begin == '0')
			return NULL;
		p_begin++;
	}
	return p_begin;
}
1
2
3
4
5
6
7
8
9
10
11

एतेन कार्येण सिद्धं कार्यं सरणीयां वर्णस्य उपलिपिं अन्वेष्टुं भवति ।
अत्र धावनस्य संख्या अनिश्चिता अस्ति
एकस्मिन् एव समये F(N)=1 इति ज्ञातुं शक्यते
मध्ये F(N)=N/2 इति ज्ञातुं शक्यते
अन्ते लभ्यते, अथवा NULL प्रत्यागच्छति यदि न लभ्यते, F(N)=N
बिग ओ सर्वाधिकं दुष्टं परिदृश्यं गृह्णाति:
कालजटिलता O(N) अस्ति ।

6. Func5 इत्यस्य समयजटिलतायाः गणनां कुर्वन्तु

void func5(int n)
{
	int cnt = 1;
	while (cnt < n)
	{
		cnt *= 2;
	}
}
1
2
3
4
5
6
7
8

इयं धावनस्य संख्या n इत्यस्य आकारेण सह सम्बद्धा अस्ति, परन्तु इयं n वारं न लूप् करोति यतोहि लूप् चरः लूप् इत्यस्य समये 2 इत्यनेन गुणितः भविष्यति, तथा च लूप् दशवारं धावित्वा शीघ्रं बहिः कूर्दति लूप् चर cnt इत्यस्य मूल्यं 1024 यावत् भविष्यति ।
चक्रसङ्ख्यां x इति कल्पयित्वा तर्हि 2^x=न
x=logn
अतः कालजटिलता अस्ति : O(longn) .

7. BubbleSor इत्यस्य जटिलतायाः गणनां कुर्वन्तु

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;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

एतत् कार्यं bubble ascending sorting पूर्णं करोति
अत्र पाशः अस्ति ।
पाशानां संख्या अनिर्धारिता अस्ति
दुष्टतमं परिदृश्यं यत् बाह्यपाशः n वारं चालयति
ततः अन्तः पाशः (n-1)+(n-2)+(n-3)+......+2+1+0 चालयिष्यति
गणितक्रमः, योगः च अस्ति : १.

कालजटिलता अस्ति : O(N) .

अन्तरिक्षजटिलता : १.

अतिरिक्तं अनुप्रयोगस्थानं नास्ति, प्रयुक्तं स्थानं च नित्यं भवति ।
ओ(१) ९.

8. कारकपुनरावृत्तिगणनायाः जटिलता Fac

long long Fac(size_t N)
{
	if (0 == N)
		return 1;
	return Fac(N - 1) * N;
}
1
2
3
4
5
6

कालजटिलता : १.

पुनरावृत्ति N वार
अतः कालजटिलता अस्ति : O(N) .

अन्तरिक्षजटिलता : १.

प्रत्येकं पुनरावृत्तिः भवद्भिः स्थानार्थं आवेदनं कर्तव्यम् ।
N वारं पुनरावृत्तिः कृत्वा N वारं स्थानस्य कृते प्रयुक्तवान्।
अन्तरिक्षजटिलता अस्ति : O(N) .