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

एल्गोरिदम श्रृङ्खला--विभाजनं विजयं च क्रमणं|त्वरितक्रमणस्य पुनः चर्चा|त्वरितक्रमणस्य अनुकूलनं|त्वरितचयन एल्गोरिदम

2024-07-12

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

भूमिका: अयं लेखः द्रुतक्रमण-अल्गोरिदमस्य प्रारम्भिक-शिक्षणस्य विषये केषाञ्चन संशयानां विस्तृत-उत्तराणि प्रददाति, तथा च मूलभूत-द्रुत-क्रमण-अल्गोरिदम् इत्यस्य अनुकूलितं संस्करणं प्रददाति

1. पुनः द्रुतक्रमणस्य विषये वदामः

द्रुतक्रमण-अल्गोरिदम् इत्यस्य मूलं अस्ति分治思想,विभाजनं विजयं च रणनीतिः निम्नलिखितत्रयेषु ,पदेषु विभक्तः अस्ति:

  1. अपघटनम् : मूलसमस्यायाः विघटनं कृत्वा अनेकेषु समानेषु, लघुषु उपसमस्यासु विघटनं कुर्वन्तु
  2. समाधानम् : यदि उपसमस्या लघु अस्ति तर्हि प्रत्यक्षतया समाधानं कुर्वन्तु अन्यथा उपसमस्यायाः पुनरावर्तनीयरूपेण समाधानं कुर्वन्तु
  3. विलयम् : मूलसमस्यायाः समाधानं अनेकानाम् उपसमस्यानां समाधानस्य विलयस्य समं भवति ।

द्रुतक्रमण-अल्गोरिदम्-इत्यत्र प्रयुक्तम् :

  1. अपघटनम् : द्रुतक्रमण-अल्गोरिदम् यत् साधयितुम् इच्छति तत् सम्पूर्णं सरणीं क्रमयितुम् इच्छति, परन्तु स्केलः विशालः अस्ति, अतः तस्य समाधान-रणनीतिः "एकं बेन्चमार्क-तत्त्वं चयनं कृत्वा सरणीं विभक्तुं" अस्ति two parts, with elements on the left that are smaller than the benchmark element , दक्षिणभागे सर्वे तत्त्वानि reference elements इत्यस्मात् अधिकाः सन्ति।" उपर्युक्तप्रक्रियायाः पुनरावृत्तिः कृत्वा, भवान् सम्पूर्णस्य सरणीयाः क्रमणं सम्पूर्णं कर्तुं शक्नोति। एतत् कार्यं on पूर्णं कृत्वा the entire array, क्रमशः वाम-दक्षिण-अन्तरालयोः उपरिष्टाद् प्रक्रियां कुर्वन्तु ।
  2. शीघ्रं द्वयोः उपसरणयोः पुनरावर्तनीयरूपेण क्रमणं कुर्वन्तु यावत् प्रत्येकस्य उपसरण्याः दीर्घता 0 अथवा 1 न भवति, यस्मिन् बिन्दौ सरणीः क्रमबद्धाः भवन्ति ।
  3. यतः पुनरावृत्तिकाले उपसरणयः पृथक् क्रमेण क्रमिताः सन्ति, अतः अतिरिक्तं विलयनपदं आवश्यकं नास्ति ।

2. संहिता कार्यान्वयनम् विस्तृतव्याख्यानं च

द्रुतक्रमणस्य मुख्यसङ्केतः अस्ति如何根据基准元素划分数组区间(parttion), विघटनविधयः बहवः सन्ति, अत्र एकः एव विधिः प्रदत्तः ।挖坑法
संहिता : १.

class Solution {
    public int[] sortArray(int[] nums) {
        quick(nums, 0, nums.length - 1);
        return nums;
    }

    private void quick(int[] arr, int start, int end) {
        if(start >= end) return;// 递归结束条件
        int pivot = parttion(arr, start, end);
		
		// 递归解决子问题
        quick(arr, start, pivot - 1);
        quick(arr, pivot + 1, end);
    }

	
	// 挖坑法进行分解
    private int parttion(int[] arr, int left, int right) {
        int key = arr[left];
        while(left < right) {
            while(left < right && arr[right] >= key) right--;
            arr[left] = arr[right];
            while(left < right && arr[left] <= key) ++left;
            arr[right] = arr[left];
        }
        arr[left] = key;
        return left;
    }
    
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30

विस्तृत उत्तराणि : १.
1.किमर्थम्start>=endकिं पुनरावृत्तेः अन्त्यस्थितिः ?

उपसमस्यायाः निरन्तरं विघटनं कुर्वन्तु उपसमस्यायाः अन्तिमः आकारः १ भवति, अर्थात् केवलम् एकः एव तत्त्वः अस्ति अस्मिन् समये आरम्भ-अन्त-सूचकाः एकस्मिन् एव तत्त्वे सूचयन्ति कालः।

2. वामस्य स्थाने प्रथमं दक्षिणं किमर्थं गन्तव्यम् ?

प्रथमं कः गच्छति इति अवलम्बते基准元素的位置,उपर्युक्ते कोड् मध्ये आधारतत्त्वं (key) वामतमं तत्त्वम् अस्ति यदि प्रथमं चालितम् अस्तिleft, left प्रथमं आधारतत्त्वात् बृहत्तरं तत्त्वं सम्मुखीभवति, ततः निष्पादयतिarr[right] = arr[left],असञ्चितत्वात्arr[right], एतत् तत्त्वं नष्टं भविष्यति
यदि भवान् प्रथमं दक्षिणतः गच्छति तर्हि दक्षिणतः प्रथमं आधारतत्त्वात् लघुतरं तत्त्वं सम्मुखीभवति, ततः निष्पादयतिarr[left]=arr[right], यतः अस्मिन् समये वामपक्षः न गतः, अद्यापि सः पिवट् अस्ति, परन्तु पिवट् अस्माभिः कीलस्य उपयोगेन रक्षितः अस्ति ।

3.किमर्थं arr[right]&gt;=key?&gt;किं न सम्भवति?

अधिकं वा समं वा मुख्यतया संसाधनार्थम् अस्ति重复元素问题
यथा - सरणी अस्ति[6,6,6,6,6]यदि &gt; अस्ति तर्हि दक्षिणसूचकः न गमिष्यति, वामः सूचकः अपि न चलति, अनन्तपाशस्य च अटति ।

4. किमर्थं गर्तखननविधिः इति कथ्यते ?

यदा r सूचकः प्रथमस्य सम्मुखीभवतिarr[r] = arr[l], अस्मिन् समये ल स्थितिः शून्या भवति, गर्तं निर्मायते ।

3. द्रुतक्रमणस्य अनुकूलनम्

मुख्यतया अनुकूलनदिशौ स्तः : १.

  1. बेन्चमार्कमूल्यपिवट् इत्यस्य चयनं सिद्धं कर्तुं शक्यते यत् यदा बेन्चमार्कमूल्यं यादृच्छिकरूपेण चयनं भवति तदा द्रुतक्रमणस्य समयजटिलता समीपं गच्छतिO(N*logN), अर्थात् उत्तमकालजटिलता
  2. पुनरावर्तिततत्त्वानां संसाधनम् : यदि अन्तरालस्य अन्तः पुनरावर्तिततत्त्वानां बहूनां संख्या अस्ति, तर्हि द्रुतक्रमण-एल्गोरिदमस्य उपरिष्टाद् संस्करणं अनावश्यक-क्रियाणां न्यूनीकरणार्थं समानानि तत्त्वानि बहुवारं पुनरावृत्तिं करिष्यति数组分三块तस्मिन् एव काले यदि भवान् विशेषपरीक्षाप्रकरणानाम् (क्रमिकसरणौ अथवा विपरीतसरणौ) सम्मुखीभवति तर्हि समयजटिलता यावत् अवनतिः भविष्यतिO(N^2)

प्रथमं प्रश्नस्य आधारेण (वर्णेन क्रमयन्तु) किम् इति अवगच्छन्तु数组分三块
विश्लेषणं कुरुत

अत्र चित्रविवरणं सम्मिलितं कुर्वन्तु
संहिता : १.

class Solution {
    public void sortColors(int[] nums) {
        // 分治 --
        // 1.定义三指针
        int i = 0;// 遍历整个数组
        int l = -1, r = nums.length;

        while(i < r) {
            if(nums[i] == 0) swap(nums,++l,i++);
            else if(nums[i] == 1) i++;
            else swap(nums,--r,i);
        }
        return;
    }

    private void swap(int[] nums,int x,int y) {
        int tmp = nums[x]; nums[x] = nums[y]; nums[y] = tmp;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • सूचनाl,r的起始位置, प्रथमतत्त्वं अन्तिमतत्त्वं च अन्तर्भवति未处理状态, अतः `l, r एतौ तत्त्वौ दर्शयितुं न शक्नोति, अन्तरालात् बहिः भवितुमर्हति
  • तथाकथितं सरणी त्रिधा विभक्तं भवति, यस्य अर्थः उपयोगः भवति三个指针去分别维护四个区间, एकः अन्तरालः अस्ति未处理区间, यथा यथा cur सूचकः निरन्तरं गच्छति तथा सर्वे अन्तरालाः संसाधिताः भवन्ति, अन्ते च केवलं त्रयः अन्तरालाः सन्ति ।

उपर्युक्तविचाराः प्रयोजयन्तु快速排序的parttion中, अन्तिमफलं त्रिषु अन्तरेषु विभक्तं भवति
अत्र चित्रविवरणं सम्मिलितं कुर्वन्तु
संहिता : १.

class Solution {
    // 快速排序优化版
    // 分解--解决--合并
    public int[] sortArray(int[] nums) {
        qsort(nums, 0, nums.length - 1);
        return nums;
    }

    private void qsort(int[] nums, int start, int end) {
        if(start >= end) return;// 递归结束条件
        // 分解
        int pivot = nums[start];
        int l = start - 1, r = end + 1, i = start;
        while(i < r) {
            int cur = nums[i];
            if(cur < pivot) swap(nums, ++l, i++);
            else if(cur == pivot) ++i;
            else swap(nums, --r, i);
        }

        // [start, l]  [l+1, r-1]  [r, end]
        // 递归解决
        qsort(nums, start, l);
        qsort(nums, r, end);
    }

    private void swap(int[] nums,int i, int j) {
        int tmp = nums[i];  nums[i] = nums[j]; nums[j] = tmp;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30

अत्र चित्रविवरणं सम्मिलितं कुर्वन्तु
2. आधारमूल्यं यादृच्छिकरूपेण चिनोतु
यादृच्छिकसङ्ख्यानां उपयोगेन आधारमूल्यं यादृच्छिकरूपेण चिनोतु

        int pivot = nums[start + new Random().nextInt(end - start + 1)];
        //               起始位置      随机产生的偏移量


  • 1
  • 2
  • 3

सम्पूर्णतया उन्नतसङ्केतः : १.

class Solution {
    // 快速排序优化版
    // 分解--解决--合并
    public int[] sortArray(int[] nums) {
        qsort(nums, 0, nums.length - 1);
        return nums;
    }

    private void qsort(int[] nums, int start, int end) {
        if(start >= end) return;// 递归结束条件
        // 分解
        int pivot = nums[start + new Random().nextInt(end - start + 1)];
        int l = start - 1, r = end + 1, i = start;
        while(i < r) {
            int cur = nums[i];
            if(cur < pivot) swap(nums, ++l, i++);
            else if(cur == pivot) ++i;
            else swap(nums, --r, i);
        }

        // [start, l]  [l+1, r-1]  [r, end]
        // 递归解决
        qsort(nums, start, l);
        qsort(nums, r, end);
    }

    private void swap(int[] nums,int i, int j) {
        int tmp = nums[i]; 
        nums[i] = nums[j]; 
        nums[j] = tmp;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32

अत्र चित्रविवरणं सम्मिलितं कुर्वन्तु

  • कार्यक्षमतायाः महती उन्नतिः अभवत्

4. द्रुतचयन एल्गोरिदम्

द्रुतचयन-अल्गोरिदम् अस्ति基于快速排序优化版本एक कालजटिलता केO(N)चयन-अल्गोरिदम्, उपयोग-परिदृश्यम् अस्ति第K大/前K大चयनविषयाणि यथा

01.सरणौ Kth बृहत्तमः तत्त्वः
लिङ्कः: https://leetcode.cn/problems/kth-largest-element-in-an-array/
विश्लेषणं कुरुत

  • क्रूरबलसमाधानं प्रत्यक्षतया तस्य उपयोगः एवsortक्रमबद्धं कृत्वा ततः Kth बृहत्तमं प्रति प्रत्यागच्छन्तु
  • कालजटिलता : १.O(N*logN)
  • अन्तरिक्षजटिलता : १.O(logN)पुनरावृत्तिद्वारा उत्पन्नानि आह्वानं स्तम्भयन्तु

तदनन्तरं कार्यान्वयनार्थं द्रुतचयन-अल्गोरिदम् उपयुज्यतेO(N)कालजटिलता का
संहिता : १.

class Solution {
    public int findKthLargest(int[] nums, int k) {
        return qsort(nums, 0, nums.length - 1, k);
    }

    private int qsort(int[] nums, int start, int end, int k) {
        if(start >= end) return nums[start];
        int pivot = nums[start + new Random().nextInt(end - start + 1)];
		
		// 数组分三块  <pivot  ==pivot  >pivot
        int l = start - 1, r = end + 1, i = start;
        while(i < r) {
            if(nums[i] < pivot) swap(nums, ++l, i++);
            else if(nums[i] == pivot) ++i;
            else swap(nums, --r, i);
        }

        // [start, l]  [l+1, r - 1]  [r, end]
        int c = end - r + 1, b = r - 1 - (l + 1) + 1, a = l - start + 1;
        // 分情况讨论  进行选择
        if(c >= k) return qsort(nums, r, end, k);
        else if(b + c >= k) return pivot;
        else return qsort(nums, start, l, k - b - c);// 找较小区间的第(k-b-c)大
    }

    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • द्रुतचयन-अल्गोरिदमस्य विचारः द्रुत-क्रमणस्य विचारेण सह अतीव सदृशः अस्ति यत् द्रुत-चयन-अल्गोरिदम् केवलं प्रत्येकस्य विभाजन-परिणामस्य अन्तरालस्य एकं भागं पुनरावृत्तिं करोति, द्रुत-क्रमण-वत् सम्पूर्णं अन्तरालं पुनरावृत्तिं कर्तुं स्थाने, अतः द्रुतचयन-अल्गोरिदमस्य समय-जटिलता न्यूनीकृता भवतिO(N)

व्यक्तिगत प्रोफाइल

सः ३० वर्षाणाम् अधिकं कालात् प्रौद्योगिक्याः शोधकार्यं कर्तुं समर्पितः अस्ति, तथा च जावा, लिनक्स, जावास्क्रिप्ट्, php, css इत्यादिषु विविधभाषासु प्रवीणः अस्ति, मुक्तस्रोतक्षेत्रे सः बहु योगदानं कृतवान् अस्ति विकासक दस्तावेजीकरणस्थानकं भविष्ये सन्दर्भार्थं प्रौद्योगिकीविकासे केचन विषयाः साझां कर्तुं सर्वे तत् पश्यन्तु

मम सम्पर्कसूचना

मेल