`
sillycat
  • 浏览: 2542932 次
  • 性别: Icon_minigender_1
  • 来自: 成都
社区版块
存档分类
最新评论

Algorithm Basic(1)Algorithm in Java

 
阅读更多

Algorithm Basic(1)Algorithm in Java 

1. Basic
Time  O(1), O(n),  O(n^2), O(n^3), O(2^n)
Storage 

array is set, it is fast, but the length is set.

Collection 
     —List can have repeat objects
          —ArrayList / LinkedList / Vector
     —Set can not have repeat objects
          —HashSet / TreeSet
Map
     —HashMap
     —HashTable
     —TreeMap

List is interface, Implemented by ArrayList, Vector, LinkedList

ArrayList 
     good for list and search, bad for insert and delete. 
     length is not enough, then increase by 1.5 times and array copy happened, 
     int newCapacity = oldCapacity + (oldCapacity >> 1); 
     Arrays.copyOf(elementData, newCapacity)

         Operator >> System.out.println(10 >> 1);  // 5

         System.arraycopy
     int[] ids1 = { 1, 2, 3, 4, 5 }; 
     int[] ids2 = newint[6];      

     //copy ids1 begin from index 1, copy 3 elements to ids2 from index 0      

     System.arraycopy(ids1, 1, ids2, 0, 3);      

     System.out.println(Arrays.toString(ids2));

     //[2, 3, 4, 0, 0, 0]
      even we do add(int index, object), remove, we need to do array copy…..

LinkedList good for insert and delete
        It is based on linked list.
        void linkLast(E e) {
        final Node<E> l = last;       

        final Node<E> newNode = new Node<>(l, e, null);       

        last = newNode;       

        if (l == null)           

           first = newNode;       

        else           

           l.next = newNode;       

        size++;       

        modCount++;
    }          

Vector is slow than ArrayList
        similar to ArrayList, and we have synchronized in the codes.

Bubblesort for Array

package com.sillycat.easyalgorithm.sort;

 

import java.util.List;

import java.util.Vector;

 

public class Bubblesort implements Sorter {

      @Override

      public void sort(List<Integer> list) {     

          if (list.isEmpty()) {            

             System.out.println("Vector can not be null!");            

             return;      

          }
          Integer bak;      

          boolean flag = true;      

          while (flag) {            

              flag = false;            

              for (inti = 0; i < list.size() - 1; i++) {

                 System.out.println("counting ....");                  

                 bak = list.get(i);                  

                 if (bak > list.get(i + 1)) {                    

                     flag = true;                    

                     list.set(i, list.get(i + 1));                    

                     list.set(i + 1, bak);                  

                 }            

              }      

          }

     }

     public static void main(String[] args) {      

         Vector<Integer> v1 = new Vector<Integer>();      

         v1.add(1);      

         v1.add(9);      

         v1.add(3);      

         v1.add(11);      

         v1.add(6);      

         System.out.println(v1);      

         Bubblesort sort1 = new Bubblesort();      

         sort1.sort(v1);      

         System.out.println(v1);

     }

   }

At most, if we have an array N, we need N scan we have the array in right order. a = 2, f(n)=n^2, T(n) = O(n^2)

2. How to Check if Algorithm is good or bad

Time Complexity

Space Complexity

O(1) Complexity
      Find the random number in an array, not the biggest, not the smallest, just pick first 3 numbers, sort it, pick up the middle number. O(3) + O(3) + O(1) = O(7)
      
O(log n) Complexity

10 to 3 functionality
package com.sillycat.easyalgorithm.basic;

 

public class BaseConversion {      

     public static int convert10to3(intsource){          

         String result = "";          

         while(source != 0){                

             result = source % 3 + result;                

             source = source / 3;          

         }          

         return result.isEmpty()? 0 : Integer.valueOf(result);      

     }      

 

     public static void main(String[] args) {          

         //convert 23(10) = 212(3)          

         System.out.println("23(10) = " + convert10to3(23) + "(3)");          

         //convert 0(10) = 0(3)          

         System.out.println("0(10) = " + convert10to3(0) + "(3)");          

         //convert 101(10) = 10202(3)          

         System.out.println("101(10) = " + convert10to3(101) + "(3)");      

     }

   }

Adjust to convert to N

package com.sillycat.easyalgorithm.basic;

 

public class BaseConversion {      

     public static int convert10toRate(intsource, intrate) {          

        String result = "";          

        while (source != 0) {                

            result = source % rate + result;                

            source = source / rate;          

        }          

        return result.isEmpty() ? 0 : Integer.valueOf(result);      

     }      

 

     public static void main(String[] args) {          

         // convert 23(10) = 212(3)          

         System.out.println("23(10) = " + convert10toRate(23, 3) + "(3)");          

         // convert 0(10) = 0(3)          

         System.out.println("0(10) = " + convert10toRate(0, 3) + "(3)");          

         // convert 101(10) = 10202(3)          

         System.out.println("101(10) = " + convert10toRate(101, 3) + "(3)");        

         System.out.println("==============================");          

         // convert 2(10) = 10(2)          

         System.out.println("2(10) = " + convert10toRate(2, 2) + "(2)");          

         // convert 0(10) = 0(2)          

         System.out.println("0(10) = " + convert10toRate(0, 2) + "(2)");          

         // convert 101(10) = 1100101(2)          

         System.out.println("101(10) = " + convert10toRate(101, 2) + "(2)");      

      }

    }

1 + |log3n| = O(log3n) = O(logn)


References:
http://daiziguizhong.qiniudn.com/article_20140305-18-32-10.html#rd
http://baike.baidu.com/view/7527.htm

http://javarevisited.blogspot.com/2013/03/top-15-data-structures-algorithm-interview-questions-answers-java-programming.html
http://www.cnblogs.com/wanlipeng/archive/2010/10/21/1857791.html
http://www.360doc.com/content/08/1027/15/61497_1833598.shtml

System.arraycopy(…)
http://blog.csdn.net/java2000_net/article/details/4059465


分享到:
评论

相关推荐

    Algorithm-algorithm_basic_java.zip

    Algorithm-algorithm_basic_java.zip,这是一个储存库,总结了主要在编码采访中的算法问题。它是基于Java语言编写的。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。

    Basic-algorithm-exercises:用于算法学习

    "Basic-algorithm-exercises" 是一个专为Java学习者设计的项目,旨在帮助初学者和进阶者通过实践来提升算法理解与应用能力。 这个项目的核心内容是"Basic-algorithm-exercises-master",它包含了多个子目录和文件,...

    java-basic-algorithm

    在“java-basic-algorithm”这个主题中,我们将深入探讨Java编程中的基本算法,这些算法是任何Java程序员都需要掌握的核心概念。 一、算法概述 算法是一组清晰定义的规则或步骤,用于解决特定问题或执行特定任务。...

    JavaData:Java_basic_sorting_algorithm简单

    "JavaData:Java_basic_sorting_algorithm简单"这个主题聚焦于Java中的基础排序算法,这些算法对于理解计算机科学的基本原理至关重要。下面将详细讨论几种常见的Java排序算法。 1. 冒泡排序(Bubble Sort): 冒泡...

    Genetic.Algorithms.in.Java.Basics.1484203291

    Genetic Algorithms in Java Basics...Chapter 2: Implementation of a Basic Genetic Algorithm Chapter 3: Robotic Controllers Chapter 4: Traveling Salesman Chapter 5: Class Scheduling Chapter 6: Optimization

    mastering.java

    Chapter 1: Java Basics – you will learn the basic programming elements of the Java language, including how to set up your programming environment, using a text editor and how to write a program....

    basic-oop-java-master.zip_Nice Work_cryb8x_d_drawypo

    【描述】"java compiler code source for that are nice work wassim ahmed algorithm oj" 提到的是Java编译器源代码,这部分内容可能包括了用于解决算法问题的代码,可能是在在线判题平台(Online Judge, OJ)上...

    国外数据结构和算法合集书籍的种子

    Algorithms in Java, 3rd Ed, Part 1-4 - Robert Sedgewick Algorithms in Java, 3rd Ed, Part 5 Graph Algorithms - Robert Sedgewick C Algorithms For Real Time DsP - Paul Embree C and Data Structures - P.S....

    Thinking in Patterns _ Problem Solving Techniques using Java.

    **标题与描述:“Thinking in Patterns – Problem Solving Techniques using Java”** 本标题及描述主要聚焦于通过Java语言来实现“思维模式”(Thinking in Patterns)的概念。这里提到的“思维模式”,指的是软件...

    c语言与java 经典算法实现

    C语言和Java中,通过二维数组可以方便地表示和操作矩阵,对于复杂的矩阵运算,可以利用库函数如OpenCV和BLAS(Basic Linear Algebra Subprograms)来提升性能。 接着是背包问题,这是运筹学中的一个经典问题,常...

    奔腾试题程序.zip

    以"bi"开头的文件(如`bi2015`、`biii2015`等)可能是"Basic"或"Basics"部分,它们可能涵盖Java的基础语法、类与对象、数据类型、流程控制(如if语句、for循环、while循环)、异常处理、数组和集合框架等核心概念。...

    Sammie Bae - JavaScript Data Structures and Algorithms - 2019.pdf

    and then lays out the basic JavaScript foundations, such as primitive objects and types. Then, this book covers implementations and algorithms for fundamental data structures such as linked lists, ...

    【Web大数据挖掘】PageRank具体实现、推荐系统实现、大作业、大数据挖掘项目、毕业设计+源代码+文档说明

    One result you must report is that when setting the teleport parameter to 0.85.In addition to the basic PageRank algorithm, you need to implement the Block-Stripe Update algorithm (see pages 52-61 in ...

    MD5加密算法(Java语言描述)

    MD5加密算法(Java版) 可以运行 原理  对MD5算法简要的叙述可以为:MD5以512位分组来处理输入的信息,且每一分组又被划分为16个32位子分组,经过了一系列的处理后,算法的输出由四个32位分组组成,将这四个32位...

    HIME 系列加密lib

    Every programming language that can access a standard Win32 dll can use HIME: C, C++, C#, Visual Basic 5/6, VB.Net, Delphi, PowerBASIC, PureBASIC, Liberty Basic, Euphoria, Java, Macromedia Director ...

    java8源码-Java-Interview:java面试相关的一些问题

    top.hengshare.interviewer.basic java基础 spring spring、spring组件源码分析 database 数据库 动态的切换数据源,你会怎么切?读写分离? struts 数据结构 thread 多线程、并发 有关多线程的一些小例子,在《Java...

    Geotools Java API 开发gis的参考资料

    org.geotools.geometry.iso.util.algorithm2D org.geotools.geometry.iso.util.algorithmND org.geotools.geometry.iso.util.elem2D org.geotools.geometry.iso.util.interpolation org.geotools.geometry.iso....

    Local register allocator

    1. 寄存器分配的重要性: 在计算机程序执行过程中,寄存器比内存访问速度更快。通过有效地利用有限的寄存器资源,可以减少内存访问,从而显著提升程序性能。局部寄存器分配器便是为此目标服务的,它在编译阶段进行...

Global site tag (gtag.js) - Google Analytics